C言語で、
素数を判定するのに、全ての素数で割ることによって
判定するプログラムって、どのように作ればいいんでしょうか?それを線形リストを使えっていってもわかりません。
全ての数で順に割っていって割りきれた数が割られた数と同じなら素数で、それ以外なら素数ではないというプログラムならできるんですけど。。。

このQ&Aに関連する最新のQ&A

素数」に関するQ&A: 素数は無限

A 回答 (2件)

線形リストは求まった素数を順次格納していくのに使うのだと思います。


もちろん、全ての素数で割っていくと言う時の「全ての素数」もこの線形リストの事であるのは言うまでもありません。
素数判定(複数個と考える)に先立って素数テーブルを作るのでしょうね。
配列でもできるし、そのほうが簡単なのですが、求めるべき素数の数が増えたとき有利と言うことか、あるいは単に線形リストを使わせたかったのでしょう。

判定すべき数の最大のもののルートが、割っていく素数の上限でよい事は、すでに#1の回答者:nobbさんが述べられています。
    • good
    • 0

とりあえず、「全ての数で順に~」割っていくやりかたなら、その数の平方根の値を超えない整数までで止めるようにしたらよいですよ。


 たとえば、71が素数かどうか調べるなら、71の平方根を超えない最大の整数、すなわち8までの整数で割ってみて、割り切れるものが無いなら素数、と。
大きい数ほど、割り算の回数が増えるので、とりあえず
1つの整数を調べるに費やす割り算の回数が半分近くに減りますよ(調べる整数の値が大きいほど)。
 ただ、平方根を求める処理が毎回入りますが、、、、

ちなみに、上記のやり方は、基本的に中学生が素数を調べるときに使うやり方です(笑)。

回答の方向性が違ってたらごめんなさい。
    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人が検索しているワード

このQ&Aと関連する良く見られている質問

Q素数判定プログラム

C言語で、『n以下のすべての素数を求めるプログラム』のソースリストを平方根を使ったやり方で作りたいのですが、エラーが出てしまって、どうしてもうまく作れません。
C言語初心者の上、勉強不足なのが悪いのですが・・・ぜひ教えてください!お願いします!

Aベストアンサー

「平方根を使ったやり方」というのは知らないのですが、いずれにしても
>エラーが出てしまって、どうしてもうまく作れません。
のプログラムを書いてみてはいかがですか?

エラーの部分については回答できるかも知れません。

Q素数を判定するプログラム

素数を判定するプログラムをC言語で作れという問題があったのですが、以下のものをビルドして実行したら途中で止まってしまいました。(例えば5と入力する)しかし、1以下の場合は正常にif文が評価されました。

// homework4.cpp : コンソール アプリケーションのエントリ ポイントを定義します。

#include <stdio.h>

int main(int argc, char* argv[])
{
int number;
int n;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d", &number);

if (number <= 1) {
printf("1より大きい整数を入力してください\a: ");
scanf("%d", &number);
}

for (n = 2; n = number - 1; n++) {
i = number % n;
if (i = 0) {
printf("%dは素数ではありません", number); break;
}
}

printf("%dは素数です", number);

return 0;

}
自分ではどこがおかしいのかさっぱりわかりません。よろしくお願いします。

素数を判定するプログラムをC言語で作れという問題があったのですが、以下のものをビルドして実行したら途中で止まってしまいました。(例えば5と入力する)しかし、1以下の場合は正常にif文が評価されました。

// homework4.cpp : コンソール アプリケーションのエントリ ポイントを定義します。

#include <stdio.h>

int main(int argc, char* argv[])
{
int number;
int n;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d", &number);

if (number <= 1) {
printf(...続きを読む

Aベストアンサー

> n = 2; n == number - 1; n++

にしても、真偽を取り違えていませんか。
また

n = 2; n != number - 1; n++

にしても、number = 2 だったら、どうなるでしょう。

また、自然数はそれ +1 の 1/2 までの自然数 (1 を除く) で一度も割り切れない場合は素数なので、対象自然数の -1 数まで調べる必要はありません (1/2 数より大きな約数は (対象自然数以外に) ない)。

Q素数を判定するプログラム

整数をひとつ入力して、それが素数かどうかを判定するプログラムを作ったのですが、素数でないものを入力しても「素数です」といわれます。
どうもfor文が評価されていないような気がしますが、原因がわかりません。

// homework4.cpp : コンソール アプリケーションのエントリ ポイントを定義します。

#include <stdio.h>

int main(int argc, char* argv[])
{
int number;
int n = 2;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d",&number);

while (number <= 1) {
printf("1より大きい整数を入力してください: ");
scanf("%d",&number);
}

if (number == 2) {
printf("%dは素数です\n",number);
goto OUT;
}
else {
for (; n == number - 1; n++) {
i = number % n;

if (i == 0) printf("%dは素数ではありません\n", number);
if (i == 0) goto OUT;
}
}

printf("%dは素数です\n", number);

OUT:

return 0;

}

どうかよろしくお願いします。

整数をひとつ入力して、それが素数かどうかを判定するプログラムを作ったのですが、素数でないものを入力しても「素数です」といわれます。
どうもfor文が評価されていないような気がしますが、原因がわかりません。

// homework4.cpp : コンソール アプリケーションのエントリ ポイントを定義します。

#include <stdio.h>

int main(int argc, char* argv[])
{
int number;
int n = 2;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d",&number);

while (number <= 1) {...続きを読む

Aベストアンサー

#include <stdio.h>

int
main(void)
{
int number;
int n;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d", &number);

while (number <= 1) {
printf("1より大きい整数を入力してください: ");
scanf("%d", &number);
}

if (number == 2) {
printf("%dは素数です\n", number);
return 0;
}
else {
for (n = 2; n < number; n++) {
i = number % n;

if (i == 0) {
printf("%dは素数ではありません\n", number);
return 0;
}
}
}

printf("%dは素数です\n", number);
return 0;
}

#include <stdio.h>

int
main(void)
{
int number;
int n;
int i;

printf("1より大きい整数を入力してください: ");
scanf("%d", &number);

while (number <= 1) {
printf("1より大きい整数を入力してください: ");
scanf("%d", &number);
}

if (number == 2) {
printf("%dは素数です\n", number);
return 0;
}
else {
for (n = 2; n < number; n++) {
i = numbe...続きを読む

QC言語のwhile文を使った素数判定プログラムで…

次に示すプログラムは、100までの素数を表示するものです。
見てのとおり、C言語のwhile文を使って書いてあります。

#include <stdio.h>

int main(void)
{
int a, b;
int flag = 0;

a = 2;
b = 2;

while(b <= 100){

*ここ*

while(a < b){

if(b%a == 0){
flag = 0;
break;
}

else{
flag = 1;
}

a++;
}

if(flag == 1){
printf("%dは素数\n", b);
}

b++;
}


getch();
return 0;
}

最初、手本を参考にしながら上記のように書きましたが、うまく機能せず、3から100までの数字すべてが素数であると表示されました。
どこが間違っているのかと、手本と厳密に見比べてみたら、8行目の
a = 2
が*ここ*と書いてある場所に書かれていました。
まさかないだろうと思いつつ、もとあったのを消して*ここ*に書き換えたら、正しく素数が表示されるようになりました。
値を代入する場所が違うだけで、なぜこのような違いが起こるのか全く理解できません。
教えてください。
(一応、書いておきますが使っているコンパイラはBorlandのやつです
コンパイラのせいってことはないですよね)

次に示すプログラムは、100までの素数を表示するものです。
見てのとおり、C言語のwhile文を使って書いてあります。

#include <stdio.h>

int main(void)
{
int a, b;
int flag = 0;

a = 2;
b = 2;

while(b <= 100){

*ここ*

while(a < b){

if(b%a == 0){
flag = 0;
break;
}

else{
flag = 1;
}

a++;
}

if(flag == 1){
printf("%dは素数\n", b);
}

b++;
}


getch();
return 0;
}

最初、手本を参考にしながら上記のように書きましたが、うまく機能せず、3...続きを読む

Aベストアンサー

>つまり、a = 2 はwhileの{}に入れないといけないということで、あってますか?

はい。

#2は無視か,flag = 1の誤り(変数の初期化時も)。勘違いしていた,すまん。

>下のほうは、なぜ値が増えていかないのですか?
毎回
a=0;
が実行されるから。

#1の「階乗」とは言わないだろうな。なんと言うか思いつかんけど。

Q数独解答判定プログラム

数独の解答判定プログラムを作成しているのですが、完成しません。下に僕の作ったプログラムを載せておくので間違い等の指摘をお願いします。
#include <stdio.h>

#define row 9
#define column 9

int question[row][column]={
915284376,
273916584,
468753912,
396178245,
742365891,
851492637,
629847153,
587631429,
134529768,
};
int num;
int singlenumber(void);
int saferow(int, int);
int safecolumn(int, int);
int safebox(int, int, int);

int main(void){
int judge;
for(num = 1; num <= 9; num++){
int singlenumber(void);
}
if(judge == 0){
printf("おめでとう!! 正解です。");
}else{
printf("残念!! 不正解です。");
}
return 0;
}

int singlenumber(void){
int i, j;
int row_judge;
int column_judge;
int box_judge;
int judge;
for(i = 0; i < row; i++){
int saferow(int i, int num);
}
for(j = 0; j < column; j++){
int safecolumn(int j, int num);
}
for(i = 0; i < row; i++){
for(j = 0; j < column; j++){
int safebox(int i, int j, int num);
}
}
if(row_judge == 0 && column_judge == 0 && box_judge == 0){
judge = 0;
}else{
judge = 1;
}
return judge;
}

int saferow(int i, int num){
int k;
int row_judge;
for(k = 0; k < column; k++){
if(num == question[i][k]){
row_judge = 0;
}else{
row_judge = 1;
}
}
return row_judge;
}

int safecolumn(int j, int num){
int l;
int column_judge;
for(l = 0; l < row; l++){
if(num == question[l][j]){
column_judge = 0;
}else{
column_judge = 1;
}
}
return column_judge;
}

int safebox(int i, int j, int num){
int m, n;
int box_judge01, box_judge02, box_judge03;
int box_judge11, box_judge12, box_judge13;
int box_judge21, box_judge22, box_judge23;
int box_judge0, box_judge1, box_judge2, box_judge;
for(m = 0; m < row ; m++){
if(m / 3 == 0){
for(n = 0; n < 3; n++){
if(num == question[m][n]){
box_judge01 = 0;
}else{
box_judge01 = 1;
}
}
for(n = 3; n < 6; n++){
if(num == question[m][n]){
box_judge02 = 0;
}else{
box_judge02 = 1;
}
}
for(n = 6; n < 9; n++){
if(num == question[m][n]){
box_judge03 = 0;
}else{
box_judge03 = 1;
}
}
}
if(box_judge01 == 0 && box_judge02 == 0 && box_judge03 == 0){
box_judge0 = 0;
}else{
box_judge0 = 1;
}
if(m / 3 == 1){
for(n = 0; n < 3; n++){
if(num == question[m][n]){
box_judge11 = 0;
}else{
box_judge11 = 1;
}
}
for(n = 3; n < 6; n++){
if(num == question[m][n]){
box_judge12 = 0;
}else{
box_judge12 = 1;
}
}
for(n = 6; n < 9; n++){
if(num == question[m][n]){
box_judge13 = 0;
}else{
box_judge13 = 1;
}
}
}
if(box_judge11 == 0 && box_judge12 == 0 && box_judge13 == 0){
box_judge1 = 0;
}else{
box_judge1 = 1;
}
if(m / 3 == 2){
for(n = 0; n < 3; n++){
if(num == question[m][n]){
box_judge21 = 0;
}else{
box_judge21 = 1;
}
}
for(n = 3; n < 6; n++){
if(num == question[m][n]){
box_judge22 = 0;
}else{
box_judge22 = 1;
}
}
for(n = 6; n < 9; n++){
if(num == question[m][n]){
box_judge23 = 0;
}else{
box_judge23 = 1;
}
}
}
if(box_judge21 == 0 && box_judge22 == 0 && box_judge23 == 0){
box_judge2 = 0;
}else{
box_judge2 = 1;
}
if(box_judge0 == 0 && box_judge1 == 0 && box_judge2 == 0){
box_judge = 0;
}else{
box_judge = 1;
}
}
return box_judge;
}

数独の解答判定プログラムを作成しているのですが、完成しません。下に僕の作ったプログラムを載せておくので間違い等の指摘をお願いします。
#include <stdio.h>

#define row 9
#define column 9

int question[row][column]={
915284376,
273916584,
468753912,
396178245,
742365891,
851492637,
629847153,
587631429,
134529768,
};
int num;
int singlenumber(void);
int saferow(int, int);
int safecolumn(int, int);
int safebox(int, int, int);

int main(void){
int judge;
...続きを読む

Aベストアンサー

int question[row][column]={
915284376,
273916584,
468753912,
396178245,
742365891,
851492637,
629847153,
587631429,
134529768,
};
だと要素数が9個しかないです
int question[ROW][COLUMN]={
9,1,5,2,8,4,3,7,6,
2,7,3,9,1,6,5,8,4,
4,6,8,7,5,3,9,1,2,
3,9,6,1,7,8,2,4,5,
7,4,2,3,6,5,8,9,1,
8,5,1,4,9,2,6,3,7,
6,2,9,8,4,7,1,5,3,
5,8,7,6,3,1,4,2,9,
1,3,4,5,2,9,7,6,8,
};
だと9*9の81個になります。
for(num = 1; num <= 9; num++){
int singlenumber(void);
}
関数呼び出しの時は型名は不要です
for(num = 1; num <= 9; num++){
singlenumber();
}
でいいですが多分やりたいことは
for(num = 1; num <= 9; num++){
judge = singlenumber();
}
みたいな感じでしょうか
ただこれでもループの最後の値しか判定できませんが
judge = 0;
for(num = 1; num <= 9; num++){
judge += singlenumber();
}
にすると9回全部0の時のみ正解になります。
int saferow(int i, int num){
int k;
int row_judge;
for(k = 0; k < column; k++){
if(num == question[i][k]){
row_judge = 0;
}else{
row_judge = 1;
}
}
return row_judge;
}
これはi番目の行に数字numがあるかどうかの判定のようですがこれもループの最後だけの判定になっちゃいますね。私なら
int saferow(int i, int num){
int k;
int row_judge = 1;
for(k = 0; k < column; k++){
if(num == question[i][k]){
row_judge = 0;
break;
}
}
return row_judge;
}
のようにして一致したら0を代入してループから抜けます。
columnもboxも同じバグがあります。
あと
int safebox(int i, int j, int num){
}
の i, j は使われてないので引数をなくしても良さそうですが。
それと間違いではないのですがマクロと変数を区別しやすいようにマクロは大文字で書くのが一般的なようです。

int question[row][column]={
915284376,
273916584,
468753912,
396178245,
742365891,
851492637,
629847153,
587631429,
134529768,
};
だと要素数が9個しかないです
int question[ROW][COLUMN]={
9,1,5,2,8,4,3,7,6,
2,7,3,9,1,6,5,8,4,
4,6,8,7,5,3,9,1,2,
3,9,6,1,7,8,2,4,5,
7,4,2,3,6,5,8,9,1,
8,5,1,4,9,2,6,3,7,
6,2,9,8,4,7,1,5,3,
5,8,7,6,3,1,4,2,9,
1,3,4,5,2,9,7,6,8,
};
だと9*9の81個になります。
for(num = 1; num <= 9; num++){
int singlenumber(void);
}
関数呼...続きを読む


人気Q&Aランキング

おすすめ情報