与えられた自然数nが素数であるか否かを判定する関数のプログラムを書け

1 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:50:56.592 ID:xJloPUnyd.net

っていう課題が出たんだがどう書けばいいの
言語は問わん

2 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:52:23.150 ID:W5SpmtSpd.net

プログラムやったことないんだが素数に規則性がないのに可能なのか？

3 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:52:45.813 ID:az53OvfPd.net

正しく判定しろとは言われてないから任意の数にTrue返す判定関数書けばいい

4 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:52:57.692 ID:/v1XBDvSd.net

じゃあ日本語で
「与えられた自然数nが素数であるか否かを判定する関数のプログラム」

5 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:54:29.063 ID:wpgvUUS90.net

時間がかかるけど、2以上√n以下の全ての自然数で割って、どれで割っても余りが0にならなければ素数とすれば判定できるぞ

6 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 15:59:14.245 ID:QnVhndhtM.net

n÷iのあまりを求めて、あまり0が１つの場合だけ素数
iは1〜nにしてforとか適当に繰り返しとけ

7 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:00:26.557 ID:o1/pMp9lM.net

モンテカルロ探索

8 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:15:46.361 ID:4812IMhi0.net

int work = 0;
関数(workに数字を手打ち);

double w1 = work;
double w2 = 0;
int flg = 0;

for(int i = 2 ; i < work ; i++){
w2 = w1 / i;
if( w2 が割り切れたら ){
flg = 1;
break;
}
}

if(flg == 1){
printf("%dは、約数ではない",work);
}else{
printf("%dは、約数である",work);
}

9 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:17:00.947 ID:VBEynkNz0.net

>>8
肝心な部分が無いじゃんｗ

10 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:18:26.309 ID:4812IMhi0.net

割り切れたかの判定が思いつかない
52だとすると小数点だけ取り出して
その数が１よりも大きければ割り切れていないって感じなのかな？

11 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:19:18.644 ID:z8AUk1vL0.net

Mathematica で実装する
入力を x とすると以下のようにかける


PrimeQ[x]

12 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:20:01.282 ID:4812IMhi0.net

>>9
たぶん>>10のでいけると思うけど
動かしてみないとどういう結果になるかわかんねえ
あとintとかdoubleの最高値みたいなのを例外処理とかでいれとかないとだめな予感
何桁までできるのか知らんけど

13 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:20:33.179 ID:yT9vc2FW0.net

無理

14 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:21:40.740 ID:z8AUk1vL0.net

言語はなんでもいいんだからわざわざ低レベルな言語でやる必要はない
僕の解答が最もシンプルでかつ美しいでしょう

15 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:21:41.149 ID:4812IMhi0.net

これintを１００個くらい繋げてものすごい桁数まで判定できるようにしたら
教授に気にいられるんでないか？
あと数学知らないけどその数が素数なのかっていう数式があるんでないのか？

16 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:21:52.061 ID:VBEynkNz0.net

>>10
結果を整数に代入して、割った数と掛け合わして元の数から引いて0なら割り切れた

17 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:23:27.604 ID:wpgvUUS90.net

>>10
c言語なら a%b でa/bの余り出るよ
他の言語でもできるやつあったはず

18 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:24:48.234 ID:4812IMhi0.net

>>16
なるほどわからん

>>17
ああ。そうだね%にして0以上の数は消して桁数上限まで10倍していって
1以上だったら割り切れませんでした。にできそう

19 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:25:08.925 ID:o1/pMp9lM.net

ミラー–ラビン素数判定法（英: Miller–Rabin primality test）またはラビン–ミラー素数判定法（英: Rabin–Miller primality test）は、
与えられた数が素数かどうかを判定する素数判定アルゴリズムの一種。

20 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:28:04.280 ID:4812IMhi0.net

あとは試しに外部ファイルに1行ずつ約数を手打ちしいって
読み込んで約数かどうかの一発判定とか
>>8の奴が上手く動けば
workに手打ちって部分からfor(int i = 1...)にして
約数の場合のみファイルに書き出しして
桁数上限でbreak;するようにしとけば一瞬で約数表のファイルができるね

21 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:29:32.425 ID:4812IMhi0.net

>>19
それよそれ
その数式さえコピペすりゃ
1行だぜ
大学の数学科行って助教授に数式教えてもらえばいい

22 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:34:35.798 ID:kz10cLLkp.net

for(i=n;i>0;i--){
if(n%i==0)c++;
}
if(c=2) printf("素数¥n");

23 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:36:11.926 ID:kz10cLLkp.net

>>22
c==2だった

24 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:37:44.335 ID:wE6fTrANa.net

for(i=1,i<x,i++)
{
if(x%i==0)
{print(false); break;}
if(x==i)
{print(true); break;}
}

かなり雑だけどこんな考え方でどうよ

25 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:41:27.237 ID:2KfCjIBqa.net

>>24
実行結果スクショよろ

26 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:41:31.910 ID:NKGO4Clzd.net

高速化のテクニックだけど
実はnを割り切れるかの判定は√n以下でいい
さらにnが2か3の倍数のときに処理飛ばせばかなり速くなる

27 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:43:47.774 ID:fCG60HEx0.net

素数のリスト作ってそれに入ってれば素数と表示

28 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:43:59.738 ID:wE6fTrANa.net

>>25
末尾aなんだから察してくれ

29 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:44:22.348 ID:2KfCjIBqa.net

2,3,5,7,11の倍数なら速攻外してしまったらどう？

30 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:44:55.032 ID:kz10cLLkp.net

>>26
へーなるほどタメになるわ
それ自体は使うことほとんどなさそうだけど

31 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:49:05.051 ID:az53OvfPd.net

ruby標準ライブラリに素数判定あるぞ

32 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:52:33.629 ID:2KfCjIBqa.net

素数かどうかsiriに聞けばすぐ教えてくれたよ
ペッパー君はどうだろ

33 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:53:53.198 ID:kzNZnEEg0.net

n×nの二次元配列を用意してエラトステネスの篩にかけろ

34 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:54:45.933 ID:2KfCjIBqa.net

素数判定 C言語でググったらすぐ出てきたわ

35 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:55:09.876 ID:0Lj8UGy3F.net

ミラーラビンテストって超低確率だけど素数以外も混ざっちゃうだろ

36 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 16:57:48.213 ID:2KfCjIBqa.net

>>11がベストだな

37 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:03:51.239 ID:gDrZE6jW0.net

import "Benri_chan.lib"
int main(){
int n=Input();
int[] sosuulist=Benri_chan.SosuGet();
bool atari=Benri_chan.Syogo(sosuulist,n);
if(atari){
Syuturyoku("素数です");
}else{
Syuturyoku("素数じゃ無いです");
}
return;
}

できたー

38 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:06:27.260 ID:NKGO4Clzd.net

cだとこんなん
nは自然数な

bool check(int n) {
if (n<4) {return (n!=1);}
int ns = (int)sqrt(n);
if (n%2==0||n%3==0) {return false;}
for (int k=5;k<=ns;k+=2) {
if (n%k==0) {return false;}
}
return true;
}

39 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:10:54.102 ID:NKGO4Clzd.net

やっべsqrtを1行下にしとけばよかった

40 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:16:27.415 ID:8Wbrzc7s0.net

>>38
どうせ+=2するならk=3から始めればよくね？

41 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:23:46.777 ID:+NBpK9Kvd.net

mとnが与えられた時にそれらの最小公倍数を返す関数はどうやんの？

42 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:26:04.394 ID:38fx94ky0.net

>>41
互除法で最大公約数gを求めてmn/g

43 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:31:26.890 ID:+NBpK9Kvd.net

>>42
賢いな

44 ：以下、5ちゃんねるからVIPがお送りします：2017/11/28(火) 17:34:03.635 ID:8Wbrzc7s0.net

なおオーバーフローの危険性を減らそうと思うとm/gしてからnをかけた方がよい