素數優化C

Question

我嘗試打印質數; 2至100萬。但沒有打印在控制檯上。你能檢查我的代碼嗎？我怎樣才能使這個代碼更優化？

這裏是我的代碼：

#include <stdio.h> 
#include <math.h> 

main() 
{ 
    int num, sr, num2; 

    for (num = 2; num <= 1000000; num++) { 
     sr = (int) sqrt(num); 
     for (num2 = 2; sr % num2 != 0; num2++) { 
     if (sr == num2) { 
      printf("%d\n", sr); 
     } 
     } 
    } 

} 

Answer 1

#include <stdio.h> 
    #include <math.h> 

    int main(){ 
    int num, sr, num2; 
    int isPrime = 1; // this is a check parameter; isPrime = 0 if number is not prime. 
    for(num=2; num<=100; num++){ 
     sr = (int) sqrt(num); 
     for(num2=2; num2 <= sr; num2++){ 
      //num2 <== sr to stop the innner loop 
      if(num%num2 == 0){ 
       //printf("=========== %d|%d\n", num,num2); // uncomment this to see if a number is divisable 
       isPrime = 0; // this number is not prime, cos num can be divided by num2 
       break; 
      } 
     } 
     if(isPrime){ 
      printf("Prime number is %d\n", num); 
      isPrime = 1; // reset the check parameter 
     }else{ 
      isPrime = 1; // reset the check parameter 
     } 
    } 
     return 0; 
    } 

此代碼的工作。既然它有用，我會讓你玩並優化它。如果你不能讓我們知道。我們會盡力幫助你。

我喜歡你如何使用sqrt來優化代碼。

Answer 2

它是否編譯？

第4行：main()應該是intmain()？

另一件事：SR = 1 1模任何數量是1

和最後。 sr永遠不會等於num2，因爲sr是1而num2是2或更大，所以它永遠不會打印任何東西。

這將讓你進入一個無限循環，什麼也不做

Answer 3

如果你想優化它，你應該使用像eratosthenes的篩子。它很容易操作你的數據範圍。你可以閱讀更多關於它在這裏： ，您可以使用http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Answer 4

一種優化的事實是，3以上的所有素數形式6N + 1或6N-1和事實的，如果一個數整除由素數，它不是素數。下面是一些使用該事實的代碼：

#include <stdio.h> 
#include <math.h> 

int is_prime(long num) 
{ 
    int k = 1, a = 0, b = 0; 
    long sr; 
    switch(num) 
     { 
     case 1: return 0; 
     case 2: return 1; 
     case 3: return 1; 
     case 4: return 0; 
     case 5: return 1; 
     case 6: return 0; 
     case 7: return 1; 
    } 
    if (num % 2 == 0) return 0; 
    if (num % 3 == 0) return 0; 
    sr = (int) sqrt(num); 
    while (b < sr) { 
     a = (6 * k) - 1; 
     b = (6 * k) + 1; 
     if (num % a == 0) 
      return 0; 
     if (num % b == 0) 
      return 0; 
     k += 1; 
    } 
    return 1; 
} 

void main(void) 
{ 
    int j; 

    for (j = 0; j<100; j++){ 
     if (is_prime(j)) 
      printf("%d is a prime\n", j); 
    } 
} 

如果num是素數，則此函數返回1。