エラトシニふるい

エラトセニふるい法は一定範囲の素数を求めるために用いられる.
1つ目の方法:
原理は配列要素に数値を格納し、非素数と判定されるとその値を0に変更し、出力時に値が0の要素をスキップする.

  
  
  
  

   
   
   
   
//         
   
   
   
   
  
   
   
   
   
#include <iostream> 
   
   
   
   
#include <iomanip>  
   
   
   
   
#define NUM 100 
   
   
   
   
#define W 2 
   
   
   
   
using namespace std; 
   
   
   
   
  
   
   
   
   
int main(int argc,char * argv[]) 
   
   
   
   
{ 
   
   
   
   
    int array[NUM/2]; 
   
   
   
   
    int sign,flag; 
   
   
   
   
  
   
   
   
   
    //      
   
   
   
   
    for(sign=0,flag=3;sign<NUM/2-1;sign++) 
   
   
   
   
    { 
   
   
   
   
        array[sign]=flag; 
   
   
   
   
        flag+=2; 
   
   
   
   
    }  
   
   
   
   
  
   
   
   
   
    //        
   
   
   
   
    for(sign=0;sign<NUM/2-1;sign++) 
   
   
   
   
    { 
   
   
   
   
        if(array[sign]) 
   
   
   
   
        { 
   
   
   
   
            for(flag=sign+1;flag<49;flag++) 
   
   
   
   
            { 
   
   
   
   
                if(!(array[flag]%array[sign])) 
   
   
   
   
                { 
   
   
   
   
                    array[flag]=0; 
   
   
   
   
                } 
   
   
   
   
            } 
   
   
   
   
        } 
   
   
   
   
    }  
   
   
   
   
  
   
   
   
   
    //      
   
   
   
   
    cout<<"100      ：
 2\t"; 
   
   
   
   
    flag=1; 
   
   
   
   
    for(sign=0;sign<NUM/2-1;sign++) 
   
   
   
   
    { 
   
   
   
   
        if(array[sign]) 
   
   
   
   
        { 
   
   
   
   
            cout<<setw(W)<<array[sign]<<'\t'; 
   
   
   
   
            flag+=1; 
   
   
   
   
            if(!(flag%5)) 
   
   
   
   
            { 
   
   
   
   
                cout<<endl; 
   
   
   
   
            } 
   
   
   
   
        } 
   
   
   
   
    }  
   
   
   
   
    cout<<endl; 
   
   
   
   
  
   
   
   
   
    return 0; 
   
   
   
   
} 
  
  
  
  

コードにNUM/2-1が繰り返される理由:if sign<=50最終判定の数字が3+2*50=103上限100 if sign<=49最終判定の数字が3+2*49=101上限100 if sign<49を超えた(すなわちsign<=48)最後に判定された数字は3+2*48=99の範囲内であり、なぜNUM/2-1なのかは原理的にどのように解釈するか分からないが、運転中に結果を観察しただけの結論である.
別の方法:
配列の下付き文字で数値を格納し、配列内の各要素の値は0と1で素数を表す.最終出力値が1の配列要素の下付き文字.原理は、1つの数を発見し、後のすべての数からその倍数を削除することです(0を割り当てます).

  
  
  
  

   
   
   
   
//         
   
   
   
   
  
   
   
   
   
#include <iostream> 
   
   
   
   
#include <iomanip> 
   
   
   
   
#define N 100 
   
   
   
   
#define W 2 
   
   
   
   
using namespace std; 
   
   
   
   
  
   
   
   
   
int main(int argc,char *argv[]) 
   
   
   
   
{ 
   
   
   
   
    int array[N]={0},sign,flag,i=0; 
   
   
   
   
  
   
   
   
   
    cout<<N<<"      ："<<endl;  
   
   
   
   
    for(sign=2;sign<N;sign++) 
   
   
   
   
    { 
   
   
   
   
        if(array[sign]==0) 
   
   
   
   
        { 
   
   
   
   
            cout<<setw(W)<<sign<<" "; 
   
   
   
   
            i++; 
   
   
   
   
            //   5       
   
   
   
   
            if(i%5==0) 
   
   
   
   
            { 
   
   
   
   
                cout<<endl; 
   
   
   
   
            } 
   
   
   
   
        } 
   
   
   
   
        for(flag=1;sign*flag<=N;flag++) 
   
   
   
   
        { 
   
   
   
   
            array[sign*flag]=1; 
   
   
   
   
        } 
   
   
   
   
    } 
   
   
   
   
  
   
   
   
   
    return 0; 
   
   
   
   
}