5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

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

1 :デフォルトの名無しさん:2010/10/22(金) 10:09:55
課題で、指定した整数nまでの素数と
その個数を求めるプログラムを作る課題が出たんですが
誰か作り方を教えてくれませんか?

2 :デフォルトの名無しさん:2010/10/22(金) 11:08:37
nまでの配列
2の倍数にチェック
3の倍数にチェック
4はチェックついてるからスキップ
以下同様

3 :デフォルトの名無しさん:2010/10/22(金) 11:10:34
2ギガ超えるなら、配列を関数にして、
複数配列やビット表現でやる

4 :デフォルトの名無しさん:2010/10/22(金) 11:15:43
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

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

                  京都大学霊長類研究所

5 :デフォルトの名無しさん:2010/10/22(金) 12:19:20
http://codepad.org/pE7dTw8e
総当りでやってみた
もっと効率いい方法あるとおもう

6 :デフォルトの名無しさん:2010/10/22(金) 12:35:04
一時変数が i ばっかで気持ち悪い

7 :デフォルトの名無しさん:2010/10/22(金) 12:53:58
馬鹿発見

8 :デフォルトの名無しさん:2010/10/22(金) 12:59:16
出来たよ^^
ttp://codepad.org/xpYiASJt

9 :デフォルトの名無しさん:2010/10/22(金) 15:43:56
あとは指導教官がこのスレを見つけないことを祈るのみだなw

10 :デフォルトの名無しさん:2010/10/22(金) 20:27:42
最近の学生はエラトステネスの篩も知らんのか

11 :デフォルトの名無しさん:2010/10/22(金) 21:37:00
いつまでたってもエラトステネスだっかエストラテネスだったかと迷う

12 :デフォルトの名無しさん:2010/10/22(金) 23:47:28
ミラーラビン法を使え
ソースにはちゃんと参考元も添えてなww

13 :デフォルトの名無しさん: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");
}
}


14 :デフォルトの名無しさん:2010/10/23(土) 17:45:12
>>5
素数じゃないときにisSosu==0とかもうね
iii=i/2;が甘いなルートiまでやれば十分

15 :デフォルトの名無しさん:2010/10/23(土) 18:31:51
>>12
素数テーブル作る場合はミラーラビン遅いぞ

16 :デフォルトの名無しさん:2010/10/23(土) 23:35:23
単に1つ作ってもよくてC判定だとおもうぞ
複数比較検討しましたってレポートにしなきゃ

17 :デフォルトの名無しさん:2010/10/28(木) 11:42:24
結局、素数って必要なん?
RSA暗号以外で

18 :デフォルトの名無しさん: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

できた

19 :デフォルトの名無しさん: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

修正した

20 :デフォルトの名無しさん:2010/10/28(木) 12:05:42
>>11
エストラテネス?
オレはずっとエラストテネスと間違えてたぞ。
アリストテレスとかいう奴のせいだが。

21 :デフォルトの名無しさん:2010/10/28(木) 12:23:21
>>18-19
これ何の言語?

22 :デフォルトの名無しさん:2010/10/28(木) 12:36:15
>>1
それは、素数判定とは言わないんじゃ。

23 :デフォルトの名無しさん:2010/10/28(木) 13:26:27
>>21
たぶんBASIC系の方言だと思うが…なんだろう?

24 :デフォルトの名無しさん: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


25 :デフォルトの名無しさん:2010/10/30(土) 09:48:39
だから何言語なんだよw

26 :デフォルトの名無しさん:2010/10/30(土) 23:34:14
Sosu no Kazu

Sosu no Kaze
と読んでしまった俺はJPOP脳

27 :デフォルトの名無しさん: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


28 :デフォルトの名無しさん:2010/11/04(木) 15:19:47
>>1

素数について
http://hibari.2ch.net/test/read.cgi/tech/1288361024/8


29 :デフォルトの名無しさん: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

30 :デフォルトの名無しさん:2010/11/04(木) 15:28:10
>>29
Syntax Error.

31 :デフォルトの名無しさん:2010/11/04(木) 15:31:33
SAVE "SOSU.BAS"
Ok.

32 :デフォルトの名無しさん:2010/11/04(木) 15:33:12
save "SOSU.BAS",P

33 :デフォルトの名無しさん:2010/11/04(木) 19:35:37
ピー ガー

当時は、セーブ中は何故か音を立てないように息を止めてた
雑音が入ると正しくセーブされないと思い込んでたんだと思う

34 :デフォルトの名無しさん:2010/11/06(土) 10:57:10
自分でもソースリスト見られなくなったことは良くあった

35 :デフォルトの名無しさん:2010/11/06(土) 11:13:11
ふん、当時はまずリストを紙に書いて、それをパソコンに入力するってのが当たり前だった。

36 :デフォルトの名無しさん:2010/11/08(月) 09:47:12
確かにbasic用は勿論、c用のコーディングシートまであったな。
尤も、未だに某社のコーディング規約ではカラム指定が生きているけど。

37 :デフォルトの名無しさん: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));

38 :デフォルトの名無しさん: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");
}


39 :デフォルトの名無しさん:2011/03/14(月) 13:37:33.43
J言語で

IsPrime =: 1&p:

40 :デフォルトの名無しさん:2011/03/14(月) 17:08:15.84
>>37
剰余を使うのが下手くそ。

41 :デフォルトの名無しさん: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;
}

42 :デフォルトの名無しさん:2011/03/17(木) 16:38:53.30
>>17
数学に疎い俺が受け売りで答えてみる。
純粋数学は現実社会においての実用性という意味では
あまり役に立たない。
ただし、応用数学を使う分野は金融工学、材料工学、統計力学などと幅広い。
だから、数論自体に実用性が無くても、数論研究での成果が社会に
生かされることはある。

実用性はさておき、研究なんて好きじゃないとやってらんないんだろうけど。

43 :デフォルトの名無しさん:2011/03/23(水) 10:00:22.15

               YES → 【素数だった?】 ─ YES → じゃあ聞くな死ね
             /                  \
【素数か判定した?】                      NO → なら、素数じゃねぇよ
             \
                NO → 死ね

44 :福盛俊明:2011/03/23(水) 23:51:00.37
アハ〜♪”

45 :デフォルトの名無しさん:2011/03/24(木) 11:21:30.87
>>17
2とか3とか17とか無かったら困るじゃないか

46 :デフォルトの名無しさん:2011/03/24(木) 13:06:59.47
VIPじゃあるまいしこんなスレがこんなに伸びてることにショック
プログラム板ってレベル低いんだな

47 :デフォルトの名無しさん: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としている。
}
    

48 :デフォルトの名無しさん: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);
}

49 :デフォルトの名無しさん:2011/03/24(木) 19:23:29.18
>>48
malloc,realloc の引数にsizeof(int)を掛けて、ゼロクリアしなきゃいかんね

50 :デフォルトの名無しさん:2011/03/24(木) 19:31:37.41
>>49
そこから突っ込むのか?
しかも微妙な言い回しで…
突っ込みどころだらけで、何を突っ込めば良いか分からんが
取りあえず最初は、free()しろってところからじゃないのか?

51 :デフォルトの名無しさん:2011/03/26(土) 10:37:37.65
ここでhaskellの出番だろうか。。。


52 :デフォルトの名無しさん:2011/03/27(日) 16:21:32.05
色んな言語の例が出てるからHaskellも出していいんじゃね
…とは言ってもググったら良い例が沢山出てきたから今更書くまでもないとは思うが

13 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)