Язык С. Простые числа.

[fufayka]

Здравствуйте! Помогите, пожалуйста. Нужно уменьшить время выполнения программы, как это можно сделать? заранее спасибо!

Дано n чисел. Для каждого из них определяется, простое ли оно. Если простое, выводится 1, иначе 0.

#include<stdio.h>

int main()
{
    int n, x, j, i, f;

    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);

    scanf("%d", &n);
    for(i = 0; i < n; i++){
        scanf("%d", &x);
        f = 0;
        for(j = 2; j < x; j++){
            if(x % j == 0) {printf("0\n"); f = 1; break;}
        }
        if(f == 0) printf("1\n");
    }
    return 0;
}

[GreenWizard]

Гугли решето Эратосфена

[Serge_Bliznykov]

Сообщение от GreenWizard

Гугли решето Эратосфена

да, думаю, что это оптимально.

ну можно немножко ускорить исходный код, уменьшив количество сравнений - перебирать делители нужно не до x, а до sqrt(x) (корень из x): например, тыц


но, повторю, решето Эратосфена на больших числах должно дать многократный выигрыш.

[fufayka]

Спасибо, помогло