Почему при l oop, начинающемся с int i = 6, больше времени, чем int i = 0? - PullRequest
Новая
       38

Почему при l oop, начинающемся с int i = 6, больше времени, чем int i = 0?

0 голосов
/ 03 марта 2020

Я запрограммировал Сито Эратосфена в C, но мой для l oop занимает больше времени, когда я начинаю с int i = 6. 

int *tmp = NULL;

tmp = malloc(sizeof(int) * 1000000);

tmp[0] = 2;
tmp[1] = 3;
tmp[2] = 5;

int prim_ = 3;
bool hasdiv = false;

clock_t t;
t = clock();
for(int i = 6; i < 1000000; i++) {
    for (int j = 0; j < prim_; j++){
        if (i % tmp[j] == 0) {
            hasdiv = true;
            break;
        }
    }
    if (!hasdiv) {
        prim_++;
        tmp[prim_] = i;
    }
    hasdiv = false;
}
t = clock() - t;
double tim = ((double)t) / CLOCKS_PER_SEC;

printf("%f",tim);

с 

for(int i = 6; i < 1000000; i++) {

это занимает 8,4 сек c, а с 

for(int i = 0; i < 1000000; i++) {

- 0,009 сек c. Откуда берется такое поведение?

Я использую VS 19 Community с MSV C 14.24.28314.

1 Ответ

2 голосов
/ 03 марта 2020

Во-первых, обратите внимание, что в вашем коде есть ошибка в том, что tmp[3] никогда не будет инициализирован: вы начинаете prim_ с 3 и увеличиваете его перед присвоением tmp[prim_]. Таким образом, каждый раз через l oop, когда j==3, вы читаете неинициализированную память, и ваш код имеет неопределенное поведение. Возможно, вы хотели поменять местами строки prim_++; tmp[prim_]=i; или просто написать tmp[prim_++]=i;.

. После исправления этого подумайте о том, что происходит, когда вы go через l oop набираете i==1. 1 не делится на любое целое число больше 1, поэтому ваш код сделает вывод, что оно простое, и установит tmp[3]=1. Поскольку каждое число делится на 1, то на каждой последующей итерации внешнего l oop вы выйдете из внутреннего l oop, как только j==3. Это, очевидно, сделает это намного быстрее, чем если бы j потенциально мог бы go вплоть до prim_. Это также сделает вашу программу бесполезной, так как она решит, что нет простых чисел, превышающих 5.

Большинство логик c, которые имеют дело с простыми числами, требует специального случая для числа 1, и это не исключение. Ваша программа вообще не имеет смысла начинать со значения i меньше 2.

...