質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

Q&A

解決済

4回答

11785閲覧

素数のカウント 高速化

marry0129

総合スコア51

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

1グッド

0クリップ

投稿2015/12/15 13:13

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
naoyan👍を押しています

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答4

0

質問の意図はわかりました。
それならば、ループがネックになっているので、なるべくループの回数を減らす試みをしてはどうでしょうか。
たとえば、
for(i=n+1;i<=2*n;i++){ //n+1以上2n以下の素数の個数を数える
で、偶数は素数ではないことは明白なので、偶数は飛ばす、とかが考えられます。

投稿2015/12/15 14:29

yoshi777

総合スコア674

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

こんにちは。

高速に素数判定するアルゴリズムは多数研究されています。
Wikipediaが参考になると思いますよ。

投稿2015/12/15 13:28

Chironian

総合スコア23272

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

http://rosettacode.org/wiki/Sieve_of_Eratosthenes#Cにあるコードを元に書いてみました。

c

1// See http://rosettacode.org/wiki/Sieve_of_Eratosthenes#C 2 3#include <stdio.h> 4#include <stdlib.h> 5#include <math.h> 6 7char* 8eratosthenes(int n, int *c) 9{ 10 char* sieve; 11 int i, j, m; 12 13 if(n < 2) { 14 return NULL; 15 } 16 *c = n - 1; /* primes count */ 17 m = (int) sqrt((double) n); 18 19 /* calloc initializes to zero */ 20 sieve = calloc(n+1,sizeof(char)); 21 sieve[0] = 1; 22 sieve[1] = 1; 23 for(i = 2; i <= m; i++) { 24 if(!sieve[i]) { 25 for (j = i*i; j <= n; j += i) { 26 if(!sieve[j]) { 27 sieve[j] = 1; 28 --(*c); 29 } 30 } 31 } 32 } 33 return sieve; 34} 35 36int main(int argc, char *argv[]) 37{ 38 int n = 100; 39 while(scanf("%d",&n)== 1 && n!=0) { //0でないかぎり繰り返し 40 int count_n = 0; 41 int count_2n = 0; 42 eratosthenes(n, &count_n); 43 eratosthenes(2 * n, &count_2n); 44 printf("count = %d\n", count_2n - count_n); 45 } 46 return 0; 47}

実行例

$ gcc prime.c $ ./a.out 1 count = 1 100 count = 21 10000 count = 1033 100000 count = 8392 1000000 count = 70435 0 $

投稿2015/12/26 23:21

katoy

総合スコア22324

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

自己解決

エラトステネスの篩を使ってときました。
自分の書いたプログラムを発展させたような解決方法を見つけ出したかったです。

投稿2015/12/15 14:08

marry0129

総合スコア51

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

swordone

2015/12/15 16:16

ほかの方の回答を無にして自己解決というのはマナーが良くないと思います。
k1000

2015/12/16 00:46

自己解決でもかまいませんが、この問題に興味を持った方のためにせめてその解決したというソースコードくらい転載してはどうかと思います。 この質問者の方は現時点で5回質問しているうち3回を自分の”解決しました報告”をベストアンサーにしていますが、いずれも同様の体(具体的な内容がない)のためかマイナス評価がついています。こうしたことを繰り返すと信用をなくすのではないでしょうか。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問