【C】建質數表- Sieve method＋質因數分解

The sieve method就是篩去法
開一個陣列，把每個質數的倍數都刪掉，最後留下來的就是質數。
注意我的方法是 質數flase, 合數true

Code
建質數表

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14

#define PRIME_NUM 40000 bool is_prime[PRIME_NUM]; void build_prime_tb(){     /*是質數:false, 不是質數:true*/     is_prime[0] = is_prime[1] = true;     for (int  i = 2; i <= sqrt(PRIME_NUM); i++) {         if (!is_prime[i]) {             for (int k=PRIME_NUM-1/i, j=i*k; k>=i; k--, j-=i) {                 if (!is_prime[k]) is_prime[j] = true;             }         }     } }

質因數分解，延上面建好的質數表

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

void prime_factor(int num){     int count=0;     int m = (int)(sqrt(num)+0.001);     int x = num;     int plist[100], ppow[100]; /*plist:質因數表, ppow:每個質因數出現幾次*/     for (int i=0; i< 100; i++) ppow[i]=plist[i]=0;     for (int i=2; i<=m; i++) {         if (!is_prime[i] && x%i==0) {             plist[count] = i;             ppow[count]++;             x /= i;             while (x%i == 0) {                 ppow[count]++;                 x /= i;             }             count++;         }     }     if (x>1){         plist[count]=x;         ppow[count]++;         count++;     }     printf("質因數個數 : %d\n", count);     printf("質因數 : ");     for (int i=0; i< count; i++) printf("%d, ", plist[i]);     printf("\n");     int tmp = 1;     for (int i=0; i< count; i++) tmp *= (ppow[i]+1);     printf("因數個數 : %d\n", tmp); }