ソエリクソンふるい
1265 ワード
原則:
第1~nの記録数.2を最小質量数とします.だから2つ以上は素数ではなく、記録媒体から切り落とし、スキャンしてから再び.3を最小質量数とします.3倍数を切り落とし、このままでは、素数をすべて求めます.
表に示すように、
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
-
5
-
7
-
9
-
11
-
13
-
15
-
17
-
19
-
2
3
-
5
-
7
-
-
-
11
-
13
-
-
-
17
-
19
-
コード:
素数の推定:
第1~nの記録数.2を最小質量数とします.だから2つ以上は素数ではなく、記録媒体から切り落とし、スキャンしてから再び.3を最小質量数とします.3倍数を切り落とし、このままでは、素数をすべて求めます.
表に示すように、
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
-
5
-
7
-
9
-
11
-
13
-
15
-
17
-
19
-
2
3
-
5
-
7
-
-
-
11
-
13
-
-
-
17
-
19
-
コード:
素数の推定:
bool is_prime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0)
return false;
}
return n!=1;
}
オンスクリーン法:const int MAX = 1000;
int prime[MAX];
bool is_prime[MAX];
int sieve(int n){
int p=0;
for(int i=0;i<=n;i++)
is_prime[i] = true;
is_prime[0] = is_prime[1] = false;
for(int i=2;i<=n;i++){
if(is_prime[i]){
prime[p++] = i;
for(int j=2*i;j<=n;j+=i) is_prime[j] = false;
}
}
return p;
}