トップページ⇒tech
52コメント15KB

素数判定プログラムを作れという課題が出たんだが

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん2010/10/22(金) 10:09:55
課題で、指定した整数ｎまでの素数と
その個数を求めるプログラムを作る課題が出たんですが
誰か作り方を教えてくれませんか？
0002デフォルトの名無しさん2010/10/22(金) 11:08:37
nまでの配列
2の倍数にチェック
3の倍数にチェック
4はチェックついてるからスキップ
以下同様
0003デフォルトの名無しさん2010/10/22(金) 11:10:34
2ギガ超えるなら、配列を関数にして、
複数配列やビット表現でやる
0004デフォルトの名無しさん2010/10/22(金) 11:15:43
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所
0005デフォルトの名無しさん2010/10/22(金) 12:19:20
http://codepad.org/pE7dTw8e
総当りでやってみた
もっと効率いい方法あるとおもう
0006デフォルトの名無しさん2010/10/22(金) 12:35:04
一時変数が i ばっかで気持ち悪い
0007デフォルトの名無しさん2010/10/22(金) 12:53:58
馬鹿発見
0008デフォルトの名無しさん2010/10/22(金) 12:59:16
出来たよ＾＾
ttp://codepad.org/xpYiASJt
0009デフォルトの名無しさん2010/10/22(金) 15:43:56
あとは指導教官がこのスレを見つけないことを祈るのみだなw
0010デフォルトの名無しさん2010/10/22(金) 20:27:42
最近の学生はエラトステネスの篩も知らんのか
0011デフォルトの名無しさん2010/10/22(金) 21:37:00
いつまでたってもエラトステネスだっかエストラテネスだったかと迷う
0012デフォルトの名無しさん2010/10/22(金) 23:47:28
ミラーラビン法を使え
ソースにはちゃんと参考元も添えてなｗｗ
0013デフォルトの名無しさん2010/10/23(土) 17:18:47
int i;
int n = 判定する数;
if(n == 1) {
printf("n is not a prime number.\n");
}
else {
for(i=2; n%i; i++);
if(i == n) {
printf("n is a prime number.\n");
} else {
printf("n is not a prime number.\n");
}
}
0014デフォルトの名無しさん2010/10/23(土) 17:45:12
>>5
素数じゃないときにisSosu==0とかもうね
iii=i/2;が甘いなルートiまでやれば十分
0015デフォルトの名無しさん2010/10/23(土) 18:31:51
>>12
素数テーブル作る場合はミラーラビン遅いぞ
0016デフォルトの名無しさん2010/10/23(土) 23:35:23
単に１つ作ってもよくてC判定だとおもうぞ
複数比較検討しましたってレポートにしなきゃ
0017デフォルトの名無しさん2010/10/28(木) 11:42:24
結局、素数って必要なん？
RSA暗号以外で
0018デフォルトの名無しさん2010/10/28(木) 12:02:41
Dim Suji%(2 to N)
For i=2 To N
　If Suji(i)=0 Then
　　j=2
　　Do While(i*j<N)
　　　Suji(i*j)=1
　　　j=j+1
　　Loop
　　Debug.Print "Sosu "; i
　End If
Next i

できた
0019デフォルトの名無しさん2010/10/28(木) 12:04:14
Dim Suji%(2 to N), Count%
For i=2 To N
　If Suji(i)=0 Then
　　j=2
　　Do While(i*j<=N)
　　　Suji(i*j)=1
　　　j=j+1
　　Loop
　　Debug.Print "Sosu "; i
　　Count=Count+1
　End If
Next i
Debug.Print "Sosu no Kazu "; Count

修正した
0020デフォルトの名無しさん2010/10/28(木) 12:05:42
>>11
エストラテネス？
オレはずっとエラストテネスと間違えてたぞ。
アリストテレスとかいう奴のせいだが。
0021デフォルトの名無しさん2010/10/28(木) 12:23:21
>>18-19
これ何の言語？
0022デフォルトの名無しさん2010/10/28(木) 12:36:15
>>1
それは、素数判定とは言わないんじゃ。
0023デフォルトの名無しさん2010/10/28(木) 13:26:27
>>21
たぶんBASIC系の方言だと思うが…なんだろう？
0024デフォルトの名無しさん2010/10/30(土) 06:28:51
program So
　implicit none
　integer :: i, n = 0
　integer, allocatable :: iprm(:)

　do while (n < 2)
　　print *, "整数 n:"; read *, n
　end do
　allocate(iprm(2:n))
　iprm = [(i, i = 2, n, 1)]

　do i = 2, int(n**0.5)
　　if (iprm(i) /= 0) iprm(i**2:n:i) = 0
　end do

　print "(5I10)", pack(iprm, iprm /= 0)
　print *, count([iprm /= 0]), "個"
　deallocate(iprm)
end program So
0025デフォルトの名無しさん2010/10/30(土) 09:48:39
だから何言語なんだよw
0026デフォルトの名無しさん2010/10/30(土) 23:34:14
Sosu no Kazu
を
Sosu no Kaze
と読んでしまった俺はJPOP脳
0027デフォルトの名無しさん2010/11/04(木) 15:17:17
1000 INPUT N
1010 DIM A(N)
1020 FOR I=2 TO N
1030 IF A(I)=0 THEN GOSUB 1060
1040 NEXT I
1050 END
1060 PRINT I
1070 J=2
1080 IF J*I>N THEN RETURN
1090 A(J*I)=1
1100 J=J+1
1110 GOTO 1080
0028デフォルトの名無しさん2010/11/04(木) 15:19:47
>>1

素数について
http://hibari.2ch.net/test/read.cgi/tech/1288361024/8
0029デフォルトの名無しさん2010/11/04(木) 15:25:22
>>27
1000 INPUT N
1010 DIM A(N)
1015 PRINT 2
1020 FOR I=3 TO N STEP 2
1030 IF A(I)=0 THEN GOSUB 1060
1040 NEXT I
1050 END
1060 PRINT I
1070 J=3
1080 IF J*I>N THEN RETURN
1090 A(J*I)=1
1100 J=J+2
1110 GOTO 1080
0030デフォルトの名無しさん2010/11/04(木) 15:28:10
>>29
Syntax Error.
0031デフォルトの名無しさん2010/11/04(木) 15:31:33
SAVE "SOSU.BAS"
Ok.
0032デフォルトの名無しさん2010/11/04(木) 15:33:12
save "SOSU.BAS",P
0033デフォルトの名無しさん2010/11/04(木) 19:35:37
ピー　ガー

当時は、セーブ中は何故か音を立てないように息を止めてた
雑音が入ると正しくセーブされないと思い込んでたんだと思う
0034デフォルトの名無しさん2010/11/06(土) 10:57:10
自分でもソースリスト見られなくなったことは良くあった
0035デフォルトの名無しさん2010/11/06(土) 11:13:11
ふん、当時はまずリストを紙に書いて、それをパソコンに入力するってのが当たり前だった。
0036デフォルトの名無しさん2010/11/08(月) 09:47:12
確かにbasic用は勿論、c用のコーディングシートまであったな。
尤も、未だに某社のコーディング規約ではカラム指定が生きているけど。
0037デフォルトの名無しさん2011/03/04(金) 17:01:40.43
/*
エラトステネスの篩をjavascriptで書いてみた
http://ja.wikipedia.org/wiki/%E3%82%A8%E3%83%A9%E3%83%88%E3%82%B9%E3%83%86%E3%83%8D%E3%82%B9%E3%81%AE%E7%AF%A9
*/
function makePrime(max){
var numList = [];
var primeNumList = [];
for (var i=2; i<=max; i++){
numList[i-2]=i;
}
primeNumList[0]=numList[0];

for (var k=1;primeNumList[primeNumList.length -1]*primeNumList[primeNumList.length -1]<max;k++){
primeNumList[k-1]=numList[0];
var j=0;
var temp=[];
for (var i in numList){
if (numList[i]%primeNumList[k-1] != 0){
temp[j] = numList[i];
j++;
}
}
numList=temp;
}
return primeNumList.concat(numList);
}
writeln(makePrime(100));
0038デフォルトの名無しさん2011/03/14(月) 10:41:58.11
void main(int argc, char**argv){

if(argc < 2){
printf("no param\n");
return;
}
int param;
sscanf(*(argv+1), "%d", ¶m);
int iSqrt = (int)sqrt(param);
for(int i=2; i<=iSqrt; i++){
if(!(param%i)){
printf("%u / %d = 0\n",param, i);
return;
}
}
printf("prime number\n");
}
0039デフォルトの名無しさん2011/03/14(月) 13:37:33.43
Ｊ言語で

IsPrime =: 1&p:
0040デフォルトの名無しさん2011/03/14(月) 17:08:15.84
>>37
剰余を使うのが下手くそ。
0041デフォルトの名無しさん2011/03/16(水) 09:21:43.71
>>37
普通はイメージ図の方のアルゴリズムで篩う
後は最適化のために、色々と細工する

function makePrime( max ){
var numList = [];
var primeNumList = [];
var i, j, last;
for( i = 2; i <= max; i++ ){
numList[i] = 1;
}
last = Math.floor( Math.sqrt( max ) );
for( i = 2; i <= last; i++ ) {
if( numList[i] ) {
for( j = i * i; j <= max; j += i ) {
numList[j] = 0;
}
}
}
for( i = 2; i <= max; i++ ) {
if( numList[i] ) {
primeNumList[primeNumList.length] = i;
}
}
return primeNumList;
}
0042デフォルトの名無しさん2011/03/17(木) 16:38:53.30
>>17
数学に疎い俺が受け売りで答えてみる。
純粋数学は現実社会においての実用性という意味では
あまり役に立たない。
ただし、応用数学を使う分野は金融工学、材料工学、統計力学などと幅広い。
だから、数論自体に実用性が無くても、数論研究での成果が社会に
生かされることはある。

実用性はさておき、研究なんて好きじゃないとやってらんないんだろうけど。
0043デフォルトの名無しさん2011/03/23(水) 10:00:22.15

　　　　　　　　　　　　　　　YES　→　【素数だった？】　─　YES → じゃあ聞くな死ね
　　　　　　　　　　　　　／　　　　　　　　　　　　　　　　　 ＼
【素数か判定した？】　　　　　　　　　　　　　　　　　　　　　　NO → なら、素数じゃねぇよ
　　　　　　　　　　　　　＼
　　　　　　　　　　　　　　　 NO → 死ね
0044福盛俊明2011/03/23(水) 23:51:00.37
アハ〜♪”
0045デフォルトの名無しさん2011/03/24(木) 11:21:30.87
>>17
2とか3とか17とか無かったら困るじゃないか
0046デフォルトの名無しさん2011/03/24(木) 13:06:59.47
VIPじゃあるまいしこんなスレがこんなに伸びてることにショック
プログラム板ってレベル低いんだな
0047デフォルトの名無しさん2011/03/24(木) 15:37:23.15
C言語
#include <stdio.h>

void sosu(int loop){
int kosu=0;
int yatu=1;
int c;
int i;
int p=0;
for(i = 2; i < loop+1; i++){
for(c = 1; c < i; c++){
if(i%c==0){
p++;
}
}
if(p==1){
printf("%d\n",i);
kosu++;
}
p=0;
}
printf("\n%d個",kosu);
}
int main(){
sosu(250); //仮に250としている。
}
　　　　
0048デフォルトの名無しさん2011/03/24(木) 17:14:41.08
コンパイルが通るかすらチェックしていない
#include <stdio.h>
int *primes; int size = SIZE_STEP;
int nth_prime(int n){
if(n >= size){
size = SIZE_STEP*(n/SIZE_STEP+1);
primes = realloc(primes,size);
}
if(primes[n] == 0){
int p = nth_prime(n-1);
do{p+=2}while(!is_prime(p));
primes[n]=p;
}
return primes[n];
}
int is_prime(int q){
int n = 0; int p;
for(p = nth_prime(n);p*p <= q;p=nth_prime(++n))
if(q%p == 0) return 0;
return 1;
}
int main(){
int count=0; int k;int n = 250;//入力n = 250と仮定
primes = malloc(size);
primes[0]=2; primes[1]=3;
for(k=2;k<=n;k++)
if(is_prime(k))count++,printf("%d\n",k);
printf("number of primes %d\n",count);
}
0049デフォルトの名無しさん2011/03/24(木) 19:23:29.18
>>48
malloc,realloc の引数にsizeof(int)を掛けて、ゼロクリアしなきゃいかんね
0050デフォルトの名無しさん2011/03/24(木) 19:31:37.41
>>49
そこから突っ込むのか？
しかも微妙な言い回しで…
突っ込みどころだらけで、何を突っ込めば良いか分からんが
取りあえず最初は、free()しろってところからじゃないのか？
0051デフォルトの名無しさん2011/03/26(土) 10:37:37.65
ここでhaskellの出番だろうか。。。
0052デフォルトの名無しさん2011/03/27(日) 16:21:32.05
色んな言語の例が出てるからHaskellも出していいんじゃね
…とは言ってもググったら良い例が沢山出てきたから今更書くまでもないとは思うが
■ このスレッドは過去ログ倉庫に格納されています