素数を求めるプログラミング

メッセージ

やまと

コマンドライン引数として10,000以下の自然数 n を指定し，n以下の素数の和を表示するプログラムを書け．もちろん出力されるべき値のテーブルをソースコードに書き込んではならない

という問題を教えていただけませんか？
（C言語です。始めは、#include<stdio.h>から始まります）

C1000 · #2 投稿記事 by **C1000** » 2006年6月26日(月) 19:21

ここはActiveBasicの質問版です。CのことはCの掲示板へお願いします。

konisi

素数を列挙するプログラム
を移植・改造すればいいかと思います。

ただし、C言語にはString型は無かった筈なので、少し面倒になるかと思われます。

C1000 · #4 投稿記事 by **C1000** » 2006年6月26日(月) 20:22

もしくはKonisiさんの作ったアルゴリズムを参考にするのはどうでしょう。

卓漏 · #5 投稿記事 by 卓漏 » 2006年6月26日(月) 22:14

>10,000以下の自然数 n を指定し，n以下の素数の和を表示するプログラム
↑たとえば、nが20だったら、20までの素数
2,3,5,7,11,13,17,19
をすべて足して、77(かな?)を表示させればいいということでしょうか？

自己解釈で↓にサンプルを置いておきますが、手抜きです。動作の保障しません。

Active Basicのサンプル [ここをクリックすると内容が表示されます]

あくまでもサンプルなので、これだけでは動作しません。
「#console」を一番先頭に置いたりすれば動作するかもしれません。

コード: 全て選択


Dim I As Long, N As Long, A As Long
Dim Check As Integer
Dim Num As Long   '指定された自然数が入る変数

Input "n=";Num

For I = 2 To Num
	Check = 0
	'Iが素数か調べる
	For N = I - 1 To 2 Step -1
		Print I ; " ";
		Print N ; I Mod N
		If I Mod N = 0 And Not I = N Then
			'割り切れた
			Check = -1
			N = 1
		End If
	Next N
	If Check = 0 Then
		A = A + I
	End If
Next I

Print A	'答え表示

C言語のサンプル [ここをクリックすると内容が表示されます]

あくまでもサンプルなので、これだけでは動作しません。
「#include<stdio.h>」を一番先頭に置いて、下のコードを「main(){ ～ }」で囲えば動作するかもしれません。

コード: 全て選択


long I, N, A;
int Check;
long Num;   /* 指定された自然数が入る変数 */

printf("n=");
scanf("%d", &Num);

for(I = 2, I <= Num, I++){
	Check = 0;
	/* Iが素数か調べる */
	for(N = I - 1,  I >= 2, N--){
		if (I % N == 0 && I != N){
			/* 割り切れた */
			Check = -1;
			N = 1;
		}
	}
	if (Check == 0){
		A += I;
	}
}

printf("%d", A);	/* 答え表示 */

卓漏さんのCのコードではforもそうですが，scanf/printfでlong型の変数に対して%dを使っているのが惜しいですね。%ldです。

それにしても，ActiveBasicの掲示板でCのことを訊くとはよほど焦っているのでしょうか。
もっとほかに適切な場所もあったでしょうに。
とは言え，私も頻繁にCやC++のことを引き合いに出すので，あまり堂々と言えるものではありませんが。

konisi

>>卓漏
コマンドライン引数を使うのですから、scanfで設定するのではなくargv[1]を調べて設定するほうが適切なのではないかなと。

tks · #8 投稿記事 by **tks** » 2008年4月12日(土) 18:40

Active Basicで作った、１３以上の素数を求めるプログラム

コード: 全て選択

動作保障済み
#prompt
2 Dim A As Long'素数の入力用
3 Dim B As Long'素数の計算用
4 Dim C As Long'素数の計算用
5 Dim D As Long'素数の計算用
6 Dim E As Long'素数
7 C=0:D=0:E=0
8 INPUT "13以上の数字を入力して下さい";A
9 FOR B=1 TO 13 STEP 1
10 IF A>=13 THEN 12 Else 8
11 NEXT
12 FOR C=1 TO A STEP 1
13 LET  D=C MOD 2
14 IF D=1 THEN E=E+1
15 NEXT 
16 E=E-1
17 PRINT "素数の数";E’素数の表示
18 GOTO 7 
END

konisi

>>tks
9行目と11行目の存在価値が不明です。
13行目では、数の奇数性しか判定していないように見えます。
100までに素数は25個のみの筈なのに、49と表示されます。

そして今日は4月1日ではありません。

ゲスト

何かの課題なのでしょうか？

「素数」
コマンドライン引数として10,000以下の自然数 n を指定し，n以下の素数の和を表示するプログラムを書け．もちろん出力されるべき値のテーブルをソースコードに書き込んではならない
実行例
$ ./main 2
2
$ ./main 3
5
$ ./main 4
5
$ ./main 5
10
$ ./main 6
10
$ ./main 7
17

--------------------------------------------------------------------------------

状況説明
Tokugawaさんが持っているカードには1000以下の自然数が一つ書かれている．
Tokugawaさんはそのカードを見せてはくれないが，Kawaguchi君が
カードに書かれている数字は300ですか？
という形式の質問をすると，Tokugawaさんは以下のように正直に答えてくれる．
書かれている数字は300よりも大きい．
その通りです．
書かれている数字は300よりも小さい．
何回質問しても正直に答えてくれる．

Kawaguchi君はどのように質問すればカードに書かれている数字を素早く知ることができるだろうか？
Kawaguchi君はカードに書かれている数字を知るために何回ぐらい質問する必要があるだろうか？
このことを経験的に確かめたい．

ゲスト

10000までの素数を列記し、バイナリ検索で目的の数値にたどり着くまでの回数を求めよ？Ｃで？

三毛CAT

最初の書き込みのような動作をするものをActive Basicで作ってみました。

[ここをクリックすると内容が表示されます]

10000までの所要時間:9820651ミリ秒(1回実測・目安として)

計測用ﾌﾟﾛｸﾞﾗﾑ [ここをクリックすると内容が表示されます]

konisi

暇が出来たのでもう少し速い奴を作ってみました。
こちらの環境で、20～32msで10000までの総和を求められます。

[ここをクリックすると内容が表示されます]

コード: 全て選択

#console

'計測用
Declare Function timeGetTime Lib "winmm.dll" () As DWord
Declare Function timeBeginPeriod Lib "winmm.dll" (uPeriod As DWord) As Long
Declare Function timeEndPeriod Lib "winmm.dll" (uPeriod As DWord) As Long
Dim sTime As Long,eTime As Long

Dim CommandLine As *Byte'コマンドライン文字列へのポインタ
Dim start As Long'コマンドライン文字列の内、先頭を0とみなした場合の第一引数の開始位置
Dim i=0 As Long'ループ用

timeBeginPeriod(1)
sTime=timeGetTime()

'第一引数の開始位置を特定
CommandLine=GetCommandLine()
If CommandLine[0]=34 then
	i=1
	Do
		If CommandLine>=128 then'SHIFT-JIS文字対策
			i++
		ElseIf CommandLine=34 Or CommandLine=0 then
			Exit Do
		End If
		i++
	Loop
End If
If CommandLine=0 then
	Print "引数が明らかに足りていない"
	ExitProcess(3)
End If
Do
	i++
	If CommandLine>=128 then'SHIFT-JIS文字対策
		i++
	ElseIf CommandLine=32 Or CommandLine=0 then
		Exit Do
	End If
Loop
If CommandLine=0 then
	Print "引数が明らかに足りていない"
	ExitProcess(3)
End If
start=i+1

'必要な量コピー
Dim buf[15] As Byte
memcpy(buf,CommandLine+start,min(15,lstrlen(CommandLine+start)))
buf[15]=0
'引数の内容を調整
For i=0 To 14
	If buf=32 then'区切り字句に来たら
		buf=0'終端文字に上書き
		Exit For
	End If
Next

Dim n As Long'調べる最大の値
n=Fix(Val(buf))
If n<=0 then
	Print "第一引数の値が自然数ではない"
	ExitProcess(1)
ElseIf n>10000 then
	Print "第一引数の値が10000を超えている"
	ExitProcess(2)
End If

Dim sum As Long'合計値
Dim j As Long,k As Long
For i=2 To n
	k=Fix(Sqr(i))
	For j=2 To k
		If i mod j=0 then Exit For
	Next
	If j=k+1 then sum+=i
Next

Print sum
eTime=timeGetTime()
timeEndPeriod(1)
Print eTime-sTime
ExitProcess(0)

Function min(val1 As Long,val2 As Long)
	If val1>val2 then
		min=val2
	Else
		min=val1
	End If
End Function

三毛CAT

前のと同じ感じ(位置の表示はなし)のC版です。

[ここをクリックすると内容が表示されます]

コード: 全て選択

#include <stdio.h>
#include <stdlib.h>

int main(int argc,char *argv[]) {
	double max;
	double tyousa;
	double sirabe;
	int flg;
	double total;/*totalに和が代入される*/
	total=0;
	max=atof(argv[1]);
	for(tyousa=2;tyousa<=max;tyousa++) {
		flg=1;
		for(sirabe=2;sirabe<=tyousa/2;sirabe++) {
			if((int)tyousa%(int)sirabe==0) {
				flg=0;
				break;
			}
		}
		if(flg==1)total+=tyousa;
	}
	printf("2から%1.0fまでの素数の和は%1.0fです。",max,total);
	return 0;
}

10000でかかった時間は5.63秒(1回実測)

ab.com コミュニティ

素数を求めるプログラミング

素数を求めるプログラミング

Re: 素数を求めるプログラミング

素数の和

素数の和(C)