尋找素數執行程序需要一些時間

Question

我寫了一個C程序來打印給定範圍內的素數來鍛鍊。 這是代碼：

#include <stdio.h> 
#include <stdbool.h> 

int main (void) { 
int num1,int num2; 
bool flag; 
int i,j,count=0; 

printf("Enter range 1:");scanf("%d",&num1); 
printf("Enter range 2:");scanf("%d",&num2); 

if(num1<2) 
    num1++; 

for(i=num1;i<=num2;i++){ 
    j=2; 
    while(j<i){ 
     if(i%j==0){ 
      flag=false; 
      break; 
     } 
     else{ 
      flag=true; 
     } 
     j++; 
    } 
    if(flag){ 
     printf("%d ",i); 
     count++; 
    } 
} 
printf("\n"); 
printf("Number of prime number between %d and %d is %d\n", 
              num1,num2,count); 
return 0; 
} 

代碼工作如我所料，但是當我輸入1-100000或更大的程序之間的範圍內打印像無限循環輸出，我不得不等待一段時間程序的打印所有素數。

我的問題是爲什麼程序需要一些時間來打印1-100000或更大範圍內的所有質數？

Answer 1

一些小的改進：

• 跳過所有偶數除了2。
• 條件j<i是沒有必要的，直到i的平方根爲 足夠。

但是，由於算法速度較慢，所以對於大數仍然不是很快。考慮尋找素數的有效算法，例如：Sieve of Eratosthenes。

Answer 2

爲什麼程序需要一定的時間

1. 因爲所有的程序需要一定的時間（和時間通常取決於程序所使用的算法效率）。
2. 你用了一個很低效的算法來決定的數量是否是素數
3. 你應該學習的計算複雜度（大O符號），看看有多少作業程序執行（一很多）。

Answer 3

下面的代碼會給你更好的效率。代碼中有許多不必要的檢查。

for(i=num1;i<=num2;i++) 
    { 
     flag = 0; 
     for(j=2;j<=(i/2);j++) 
     { 
     if(i%j == 0) 
     { 
      flag = 1; 
      break; 
     } 
     } 
     if(!flag) 
     { 
     printf("%d ",i); 
     count++; 
     } 
    }