для цикла C работают странно?

Question

У меня проблема с циклом в C. Целью программы является найти простые числа в известном количестве k. Вот моя программа:

unsigned int i, k, j; 
    unsigned long int prime; 

    int _tmain(int argc, _TCHAR* argv[]) { 

    printf("How many prime numbers do you want to print out in order? "); scanf_s("%u", &k); 
     printf("%u fist prime numbers are: ", k); 
     i = 1; 
     prime = 2; 
     while (i <= k) 
     { 
       for (j = 2; j <= prime; j++) 
       { 
        if (prime % j == 0) 
        { 
         if (j == prime && prime != 2) 
         { 
          printf("%lu, ", prime); 
          i++; 
         } 
         prime++; 
         j = 2; 
        } 
       } 
     } 
     _getch(); 
    return 0; 
    } 

И когда я запускаю программу, она возвращает бесконечную последовательность чисел. Но если я добавлю «else j ++;» например:

for (j = 2; j <= prime; j++) 
       { 
        if (prime % j == 0) 
        { 
         if (j == prime && prime != 2) 
         { 
          printf("%lu, ", prime); 
          i++; 
         } 
         prime++; 
         j = 2; 
        } 
           else j++; 
       } 

Тогда программа будет работать правильно. Я думаю, что это странно и не может объяснить почему?

Спасибо заранее (и извините за мой плохой английский).

Answer 1

Как я упоминал в комментариях, проблема была вызвана тем, что у вас не было «разрыва» в цикле for, чтобы заставить его вернуться во внешний цикл while, когда вы обнаружили действительный делитель.

Это было усугублено неправильным использованием имен переменных, смущающих вас - ваш исходный код, похоже, путается о том, что такое «j» и «prime».

Здесь я переработан код, чтобы быть чистым и дать значительное увеличение производительности для больших простых запросов:

#include <stdio.h> 

#define FALSE (0) 
#define TRUE (!(FALSE)) 

int main() 
{ 
    int numPrimes = 0; 
    int candidate, divisor; 
    int isPrime; 
    printf("How many prime numbers do you want to print out in order? "); 
    scanf("%u", &numPrimes); 
    printf("\n%u first prime numbers are:\n", numPrimes); 

    if (numPrimes > 0) { 
     printf("2, "); 
     --numPrimes; 
    } 

    // we only need to test odd numbers. 
    for (candidate = 3; numPrimes > 0; candidate += 2) { 
     // N/(N/2) + 1 is always < 1, so we only have to test half the values. 
     // we also only need to test odd divisors 
     isPrime = TRUE; 
     for (divisor = 3; divisor <= candidate/2; ++divisor) { 
      // it's not prime if testNumber divides in 
      if (candidate % divisor == 0) { 
       isPrime = FALSE; 
       break; 
      } 
     } 
     if (isPrime) { 
      printf("%lu, ", candidate); 
      --numPrimes; 
     } 
    } 

    printf("\n"); 

    return 0; 
} 

Live Demo здесь: http://ideone.com/yrUPBy

Который с удовольствием рассказывает мне

How many prime numbers do you want to print out in order? 
1000 first prime numbers are: 
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 
37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 
79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 
... 
7741, 7753, 7757, 7759, 7789, 7793, 7817, 7823, 7829, 7841, 
7853, 7867, 7873, 7877, 7879, 7883, 7901, 7907, 7919, 

Answer 2

Ваша петля имеет j <= prime как конечное условие, то есть последнее значение j будет равно prime. В этом случае (prime % j == 0) всегда будет правдой.

При добавлении дополнительного j++ вы пропускаете половину значений j, который случайно пропускает эту проблему. Программа по-прежнему работает неправильно.

Answer 3

Когда программа печатает простое 3, переменные имеют следующие значения:

i = 1 
j = 3 
prime = 3 

Затем увеличиваем i и prime, и установить j = 2, так что:

i = 2 
j = 2 
prime = 4 

Теперь вы возвращаетесь к верхней части петли, которая составляет j++:

i = 2 
j = 3 
prime = 4 

С j <= prime цикл продолжается. Поскольку prime % j не 0, он пропускает тело этого if, и возвращается к началу цикла, которая увеличивает j снова:

i =2 
j = 4 
prime = 4 

На этот раз prime % j == 0, поэтому она печатает prime, даже если это на самом деле не простое число.

Это происходит для каждого значения prime.

Когда вы добавляете j++ в предложение else, это приводит к тому, что в случае сбоя дважды увеличивается значение j. Так оно идет от 3 до 5, и никогда не делает это к случаю, где j == prime и он печатает номер. Затем j <= prime сбой, поэтому цикл for завершается.