程式設計訓練——質數篩法

實作一個程式，輸入n，輸出1～n的非質數，n最大為100。

【樣例】

Input
20

Output（一行輸出五個數，每個數占寬度6）
     1      2      3      5      7 
    11     13     17     19 
           

【代碼】

（所用算法和常見錯誤講解在注釋裡）

//  算法描述：任何數都可以寫成若幹質數的乘積，比如18=2*3*3，16=2^4，現将一個數分解成若幹質數的積，
//  然後将這些質數中的最小值作為p，剩餘質數的積作為q，則任何質數都能寫成(p^k)*q的形式。
//
//  指數篩法就是将一系列的數字中，非質數進行删除，比較笨的辦法是将質數從小到大排列，然後依次删除質數的若幹倍，但是這樣會有重複删除，
//  影響效率（比如删除2的若幹倍和3的若幹倍均會删除6）。
//
//  不會重複删除的方式：如果已知p是質數，先删除p的2，3……次方，然後找出比p大沒有删除的數作為q，删除pq，p^2*q,……，直到p^k*q超過範圍，則選取比q大沒有被删除的數作為新的q進行同上操作，
//  直到pq的值超過範圍，則尋找下一個比p大沒有被删除的數作為新的p，重複上面的過程。

#include<stdio.h>

#define MAXSIZE 105

//傳回比a[currentIndex]大尚未被删除的數在數組中的下标
int NextIndex(int *a,int currentIndex,int size){
    int index;
    for(index=currentIndex+1;index<size;index++){
        if(a[index]!=0)
            break;
    }
    if(index>=size){
        return -1;
    }
    else{
        return index;
    }
}

//用于計算a的b次方
int Sqrt(int a,int b){
    int result=1;
    if(b!=0){
        for(int i=1;i<=b;i++){
            result*=a;
        }
        return result;
    }
    else{
        return 1;
    }
}

int main(){
    int a[MAXSIZE];
    int size;
    int p,q;
    int printcount=0;
    while(scanf("%d",&size)==1){
        for(int i=0;i<size;i++){
            a[i]=i+1;
        }
        for(p=2;p<=size;p=NextIndex(a,p-1,size)+1){
            if(p==0)break;  //不要忽略這一句，否則容易陷入死循環
//            printf("p is %d\n",p);
            for(int i=2;Sqrt(p,i)<=size;i++){   // 易錯點：容易誤将p也删去，正确的做法是從p^2開始删除，然後依次删除p^3……
                a[Sqrt(p,i)-1]=0;
            }
            for(q=NextIndex(a,p-1,size)+1;p*q<=size;q=NextIndex(a,q-1,size)+1){     //錯點，for的第3個參數少了“+1”，導緻陷入死循環，q的值一直是4
//                printf("q is %d\n",q);
                if(q==0){
                    break;
                }
                else{
                    for(int j=1;Sqrt(p,j)*q<=size;j++){
                        a[Sqrt(p,j)*q-1]=0;
                    }
                }
            }
        }
        for(int i=0;i<size;i++){
            if(a[i]!=0){
                if(printcount%5==0){
                    printf("\n");
                }
                printf("%6d ",a[i]);
                printcount++;
            }
        }
        printf("\n");
        printcount=0;
    }
    return 0;
}