素数相関アルゴリズム

1.素性テスト
//素性テストo(sqrt(n))

1 int is_prime(int n)

2 {

3     for(int i=2;i*i<=n;i++){

4         if(n%i==0) return 0;

5     }

6     return n!=1;

7 }

//約数列挙o(sqrt(n))

 1 vector<int>  divisor(int n) {

 2     vector<int> res;

 3     for(int i=2;i*i<=n;i++) {

 4         if(n%i==0) {

 5             res.push_back(i);

 6             if(i!=n/i) res.push_back(n/i);

 7         }

 8     }

 9     

10     return res;

11 }

//整数分解o(sqrt(n))

 1 map<int,int> prime_factor(int n) 

 2 {

 3     map<int,int> res;

 4     for(int i=2;i*i<=n;i++) {

 5         while(n%i==0) {

 6             res[i]++;

 7             n/=i;

 8         }

 9     }

10     if(n!=1) res[n]=1;

11     return res;

12 }

 
2.オングスクリーン法o(nlogn)

 1 int sieve(int n)

 2 {

 3     int p=0;

 4     clr(is_prime,0);

 5     is_prime[0]=is_prime[1]=1;

 6 

 7     for(int i=2;i<=n;i++) {

 8         if(!is_prime[i]) {

 9             prime[++p]=i;

10             for(int j=2*i;j<=n;j+=i) is_prime[j]=1;

11         }

12     }

13     return p;

14 }

3.区間ふるい法

 1 void segment_sieve(LL a,LL b)

 2 {

 3     for(int i=0;(LL)i*i<b;i++) is_prime_small[i]=true;

 4     for(int i=0;i<b-a;i++)     is_prime[i]=true;

 5     

 6     for(int i=2;(LL)i*i<b;i++) {

 7         if(is_prime_small[i]) {

 8             for(int j=2*i;(LL)j*j<b;j+=i) is_prime_small[j]=false;

 9             for(LL j=max(2LL,(a+i-1)/i)*i;j<b;j+=i) is_prime[j-a]=false;

10         }

11     }

12 

13 }