素数优化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。