獲取所有素數

Question

我試圖從1到10獲得所有素數。我的代碼雖然沒有工作，但誰能告訴我爲什麼？

#include<stdio.h> 

int main(void) { 

    int i = 10; 
    int n = 10; 

    for(; i > 1; i--) { 
     while(n > 1) { 
      if((i % (n - 1)) == 0) { 
       printf("%d is not a prime number", i); 
       break; 
       n--; 
      } 
     } 
     n = 10; 
     printf("%d is a prime number", i); 
    } 
    return 0; 
} 

獲得非常大的計算時間和無輸出。

Answer 1

您的while循環進入無限循環，因爲您在if語句塊內遞減n。

將if塊的閉括號之後n--內的while循環

Answer 2

請參見下面的固定。
存在的主要問題：

1. 你的程序還沒有結束的原因被固定在第一個內部的if語句while循環 - 考慮i = 10和n-1 = 9。在這種情況下，如果句子將解析爲false並且程序將無止境地循環，因爲n--從不發生。
2. 即使你的計劃並得出結論，它總是會打印所有非素數%d is not a prime number和%d is a prime number（爲什麼？）
3. 由於您的模數約爲n-1，並n遞減爲2，每次測試數量將是一個非黃金比（您測試的是i%1）

4. 其他 - 你都好（;

   #include<stdio.h> 
   
   int main(void) { 
       int i; 
       int n; 
   
       for(i = 10; i > 1; i--) { 
        n = i; 
        while(n > 2) { 
         if((i % (n-1)) == 0) { 
          printf("%d is not a prime number\n", i); 
          break; 
         } 
         n--; 
        } 
        if (n == 2) 
         printf("%d is a prime number\n" , i); 
       } 
       return 0; 
   } 
   

Answer 3

你的邏輯是錯誤的，儘量ŧ他以下幾點：

#include<stdio.h> 

int main(void) { 
    int i = 10; 
    for(; i > 1; i--) { 
     int n = 10; 
     int flag = 0; 
     while(n > 2) { 
      if((i % (n - 1)) == 0) { 
       flag = 1; 
       printf("%d is not a prime number", i); 
       break; 
      } 
      n--; 
     } 
     if(flag == 0) { 
      printf("%d is a prime number", i); 
     } 
    } 
    return 0; 
} 

有一個問題，因爲你是你打破後decremeting，這是沒有意義的

編輯：我只是意識到這將始終打印「是一個素數」，則需要設置一個標誌來告訴你它是否是素數。

Answer 4

我們初學者應該互相幫助。

這是一個示範程序，我儘量使用你的方法。

#include <stdio.h> 

int main(void) 
{ 
    const int N = 10; 

    for (int i = N; i > 1; i--) 
    { 
     int n = i - 1; 
     while (n > 1 && i % n != 0) n--; 

     if (n == 1) 
     { 
      printf("%d is a prime number\n", i); 
     } 
     else 
     { 
      printf("%d is not a prime number\n", i); 
     } 
    } 

    return 0; 
} 

程序輸出是

10 is not a prime number 
9 is not a prime number 
8 is not a prime number 
7 is a prime number 
6 is not a prime number 
5 is a prime number 
4 is not a prime number 
3 is a prime number 
2 is a prime number 

設置不變N與任意正值你可以和包括N之前得到的所有質數。

至於你的程序，那麼你應該把第一條語句printf放在內部循環之外。此語句n--;也必須遵循if語句。當i等於2並且n也等於2時，那麼您將得到2不是質數，因爲該表達式i % (n - 1)) == 0產生了真實。

您可以編寫一個單獨的函數來檢查給定的數字是否爲素數。 你在這裏。

#include <stdio.h> 

int is_prime(unsigned int n) 
{ 
    int prime = (n == 2) || (n != 1 && n % 2); 

    for (unsigned i = 3; prime && i <= n/i; i += 2) 
    { 
     prime = n % i; 
    } 

    return prime; 
} 

int main(void) 
{ 
    while (1) 
    { 
     unsigned int n; 

     printf("Enter a non-negative number (0 - exit): "); 

     if (scanf("%u", &n) != 1 || n == 0) break; 

     printf("\nPrime numbers up to %u:", n); 

     for (unsigned int i = 0; i < n; i++) 
     { 
      if (is_prime(i + 1)) printf(" %u", i + 1); 
     } 

     printf("\n\n"); 
    } 

    return 0; 
} 

Answer 5

但願我不回答你的功課問題，但...

#include<stdio.h> 

int main() { 

int i = 10; 
int n = 10; 

for(i=10; i>1; i--) { 
    n=i;      
    while(n > 1) { 
     /* You also need to check to make sure that you aren't checking for 1 here. */ 
     if((i % (n-1)) == 0 && (n-1 !=1)) { 
      printf("\n\n %d is not a prime number",i); 
      break; 
     } 
     n--; /* This is culprit number one, your control operator is never being hit because it is after the break statement */ 
     if (n==1){ 
      /* n==1 means This should never be called unless the entire loop has proven every other number has been checked */ 
      printf("\n\n %d is a prime number" , i); 
     } 
    } 
} 
return 0; 

}

Answer 6

簡單可靠的方法做，這是通過以下方式：

#include<stdio.h> 
int main(){ 
    int i,a; 
    for(i=2;i<=10;i++){ 
     for(a=2;a<i;a++) 
      if(a%i==0) 
       break; 
     if(a==i) 
      printf("%d is a prime number",i); 
    } 
    return 0; 
} 

Answer 7

As @Zaid pointed out，無限循環是由內部的n--引起的if聲明。 if條件最終會失敗，所以它最終會陷入無限循環。

原來內部while循環是另一個循環。

for(n = 10; n > 1; n--) 

這種錯誤就是爲什麼使用循環，它明確規定了初始化，終止條件，並且遞增。

這不會使代碼工作，但它不是無限的。

---

你基本上試圖做的是每個數字，嘗試將它除以低於自身的每個數字。

for(i = 10; i > 1; i--) { // every number from 10 to 2 
    for(n = i-1; n > 1; n--) { // every number lower than i to 2. 
     if(i % n == 0) { 
      printf("%d is not a prime number\n", i); 
      break; 
     } 
    } 

    // If n reached 1, it made it through the sieve. 
    if(n <= 1) { 
     printf("%d is a prime number\n", i); 
    } 
} 

注意，通過在我開始N - 1有沒有必要記住我比較反對N - 1，簡化了代碼，這是一個可能性就越小錯誤。

---

有幾種方法可以優化它。我們可以觀察以下幾件事：當n> i/2時，一個整數永遠不可能被均勻整除。所以10永遠不會被9,8,7或6整除。這意味着我們可以在i/2處開始計數n並保存一堆檢查。由於這是整數除法，所以i/2將總是舍入，不需要自己做。

因素越小，它就越有可能成爲除數。一半數字可以被2整除，1/3可以被3整除，1/5乘以5 ...因此，從底部開始並且增加n會更快。

#include<stdio.h> 

int main(void) { 
    int num; 
    int divisor; 

    // From 10 to 2. 
    for(num = 10; num > 1; num--) { 
     // From 2 to num/2, no need to go further. 
     for(divisor = 2; divisor <= num/2; divisor++) { 
      if(num % divisor == 0) { 
       printf("%d is not a prime number\n", num); 
       break; 
      } 
     } 

     // If we got past num/2 it's prime 
     if(divisor > num/2) { 
      printf("%d is a prime number\n", num); 
     } 
    } 

    return 0; 
} 

我們可以更進一步，並觀察到偶數不是素數。這意味着偶數也永遠不是素數因數。如果我們以奇數開始，我們可以通過再次將檢查次數減半來計數。如果我們完全忽略偶數，這很容易。

#include<stdio.h> 

int main(void) { 
    int num; 
    int divisor; 

    // Count down from 11 by 2s. 
    for(num = 11; num > 1; num -= 2) { 
     // From 3 to num/2. No need to check 2, we skipped even numbers. 
     for(divisor = 3; divisor <= num/2; divisor += 2) { 
      if(num % divisor == 0) { 
       printf("%d is not a prime number\n", num); 
       break; 
      } 
     } 

     // Same end condition as before. 
     if(divisor > num/2) { 
      printf("%d is a prime number\n", num); 
     } 
    } 

    // Special case for 2. 
    printf("2 is a prime number\n"); 

    return 0; 
} 

如果你想所有的數字，你可以把一個特殊的情況下，主循環內，以檢查它是否是偶數。同樣，2是特殊的，因此我們不必在循環內持續檢查num！= 2。

#include<stdio.h> 

int main(void) { 
    int num; 
    int divisor; 

    // Count down from 10 to 3, 2 is special cased. 
    for(num = 10; num > 2; num--) { 
     // Special case for even numbers so we can still do the 
     // for loop by 2s. 
     if(num % 2 == 0) { 
      printf("%d is not a prime number\n", num); 
      continue; 
     } 

     // 3 to num/2, odd numbers only. 
     for(divisor = 3; divisor <= num/2; divisor += 2) { 
      if(num % divisor == 0) { 
       printf("%d is not a prime number\n", num); 
       break; 
      } 
     } 

     if(divisor > num/2) { 
      printf("%d is a prime number\n", num); 
     } 
    } 

    // Again, special case for 2 to reduce code operations inside the loop 
    printf("2 is a prime number\n"); 

    return 0; 
}