質數

　　定義：任何整數若其因數只有1與自身則為質數。
　　ex. 7只能因式分解成1*7，所以是質數；8因式分解為2*2*2，所以不是質數。

　　因此可以得到一演算法來驗證某數X是否為質數：用2～X-1的數值對X取餘數，若2～X-1有任何一個數值可以整除X，則X就不是質數；反之，若2～X-1都不能整除X，那X就是質數。
　　ex. X=7
　　　　X%2 = 1
　　　　X%3 = 1
　　　　X%4 = 3
　　　　X%5 = 2
　　　　X%6 = 1
　　2~6都不能整除7，則7是質數。

　　根據這想法實作出：讓使用者輸入一變數input，程式則印出1~input範圍間的所有質數，並再最後一行印出質數個數。程式如下：

#include <stdio.h>
#include <time.h>

int main() {
    int i, j ;
    int input ;
    int isPrime ;
    int count ;
    clock_t start, end ;
    printf("程式可以找出1~N範圍內的值數, 並將之列印.\n") ;
    printf("請輸入N值: ") ;
    scanf("%d", &input) ;
    do {
        start = clock() ;
        count = 0 ;
        for(i=2 ; i<=input ; i++) {
            isPrime = 1 ;
            for(j=2 ; j<i ; j++) {
                if(i%j == 0) {
                    isPrime = 0 ;
                    break ;
                }
            }
            if(isPrime) {
                printf("%4d ", i) ;
                count++ ;
            }
        }
        printf("\n共%d個\n", count) ;
        end = clock() ;
        printf("clock: %d\n", end-start) ;
    } while(scanf("%d", &input)!=EOF) ;
    return 0 ;
}

　　不過這演算法感覺上似乎有點慢，再回憶一下求質數的方法，是否記得質數的驗證不需要把2~X-1都拿來驗證？只需要驗證2~sqrt(X-1)就夠了！
　　PS.　sqrt表示開根號

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

int main() {
    int i, j ;
    int input ;
    int isPrime ;
    int count ;
    clock_t start, end ;
    printf("程式可以找出1~N範圍內的值數, 並將之列印.\n") ;
    printf("請輸入N值: ") ;
    scanf("%d", &input) ;
    do {
        start = clock() ;
        count = 0 ;
        for(i=2 ; i<input ; i++) {
            isPrime = 1 ;
            for(j=2 ; j<=sqrt(i) ; j++) {
                if(i%j == 0) {
                    isPrime = 0 ;
                    break ;
                }
            }
            if(isPrime) {
                printf("%4d ", i) ;
                count++ ;
            }
        }
        printf("\n共%d個\n", count) ;
        end = clock() ;
        printf("clock: %d\n", end-start) ;
    } while(scanf("%d", &input)!=EOF) ;
    return 0 ;
}

　　在我電腦上以1～99999來run程式，第一個演算法大概要花13828個clock執行；第二個演算法則只需要1266個clock執行。當然如果範圍越大兩者效率差別會更加明顯！