2015/04/14

【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);
}