nを読み込み、n~2nまでの素数の数を求めるプログラムを考えています。
<入力>
1
100
10000
1000000
0
<出力>
1
21
1033
8392
以下のプログラムで、素数は数えられたのですが、
数が大きくなると、かなりの時間がかかります。
どうすれば、早く数え上げることができますか??
よろしくお願いします。
C
1#include<stdio.h> 2#include<math.h> 3#define MAX 123456*123456 4 5int n,i,j; 6int count; 7 8int main(void){ 9 10 int n; 11 while(scanf("%d",&n)==1 && n!=0){ //0でないかぎり繰り返し 12 int count=0,i; 13 for(i=n+1;i<=2*n;i++){ //n+1以上2n以下の素数の個数を数える 14 int k; 15 for(k=2;i%k!=0;k++); //2~割り切れない限りkを増やして 16 if(k!=i){count++;} //自分自身以外で割り切れるものがあれば、countにいれる。 17 } 18 printf("%d\n",count); 19 } 20 21 return 0; 22} 23
回答4件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。