C言語で入力値以下の素数の最大値を求めたい

Question

前提・実現したいこと

C言語で、入力値以下（1000以下の入力値n)の素数の最大値を求めて表示したい。

該当のソースコード

#include<stdio.h>
int prime(int);

int main(void){
    int n,i,j;
    scanf("%d",&n);
    printf("入力値:%d\n",n);
    
        for(i=1000;i>1;i--){
            j=prime(i);
            if(j==2){
                break;
            }
        }
    
    printf("%d",i);
    
    return 0;
}

int prime(const int n){
    int i,j;
    j=0;
    for(i=2;i<=n;i++){
        if(n%i==0){
            j++;
        }
    }
    return j;
}

試したこと

素数を計算する関数のなかで入力してその入力値をもとに素数の計算をおこなうように考えてみました。

#include<stdio.h>
int primeNumber(int);

int main(void){
    int n,i,j;
    
    printf("入力値:%d\n",n);
    
        for(i=1000;i>1;i--){
            j=primeNumber(i);
            if(j==2){
                break;
            }
        }
    
    printf("%d",i);
    
    return 0;
}

int primeNumber(const int n){
    int i,j;
    scanf("%d",&n);
    if(n>=2&&n<=1000){
        return n;
    }
    j=0;
    for(i=2;i<=n;i++){
        if(n%i==0){
            j++;
        }
    }
    return j;
}

この場合だと永続的に入力を要求されるようになります。

補足情報（FW/ツールのバージョンなど）

visual studio codeでプログラムしています。

Answer 1

素数関連の問題はエラトステネスの篩を使えばいいです。

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

int primeNumber(const int n)
{
  bool* isprime;
  if (n < 2) {
    return -1;
  }
  isprime = (bool*)malloc((n + 1) * sizeof(bool));
  memset(isprime, true, (n + 1) * sizeof(bool));

  int res = 2;
  for (int i = 2; i <= n; i++) {
    if (isprime[i]) {
      for (int j = 2 * i; j <= n; j += i) {
        isprime[j] = false;
      }
      res = i;
    }
  }
  free(isprime);
  return res;
}
int main(void)
{
  int n;
  scanf("%d", &n);
  printf("入力値:%d\n", n);

  int res = primeNumber(n);
  if (res == -1) {
    printf("素数はありません\n");
    return 0;
  }
  printf("%d\n", res);
  return 0;
}

Comments

[tsk1999]

無事実現できました。エラトステネスの篩のアルゴリズムについての知識皆無だったので勉強になりました。ありがとうございます。

Answer 2

n は素数か？
n-1 は素数か？
n-2 は素数か？
:
:
3 は素数か？
2 は素数か？

とループ処理して最初に見つかった素数を表示して処理を終了すればいいので、

        for(i=n;i>1;i--){

というループにして、iが素数か調べて、素数なら表示して処理を終了すればいいのでは？

追記： エラストネスの篩を使った実装例を示しておきます。

#include <stdio.h>

int main(void) {
    int n;
    scanf("%d", &n);
    printf("入力値:%d\n", n);

    int primes[n + 1];
    for (int i = 0; i <= n; i++) primes[i] = (i > 3 && i % 2 == 0) ? 0 : i;
    for (int i = 2; i*i <= n; i++) if (primes[i] != 0) for (int x = i + i; x <= n; x += i) primes[x] = 0;
    while (n > 0 && primes[n] == 0) n--;
    printf("%d", n);
    return 0;
}

Comments

[uyu0531]

すみません。同じような問題を解いているものです。
for(i=n;i>1;i--){
というループにして、iが素数か調べて、素数なら表示して処理を終了すればいいのでは？
とありますが、ここについて詳しく解説いただけないでしょうか。よろしくお願いいたします。

Answer 3

for(i=1000;i>1;i--){

を

for (i = n; i > 1; i--) {

にしたらいいかと思ったらいろいろよくなかった。

#include<stdio.h>
int prime(int);

int main(void) {
    int n;
    scanf("%d", &n);
    printf("入力値:%d\n", n);

    for (int i = n; i > 1; i--) {
        if (prime(i) != 0) {
            printf("%d", i);
            break;
        }
    }
    return 0;
}

int prime(int n) {
    if (n < 2) {
        return 0;
    } else if (n == 2) {
        return 1;
    } else if (n % 2 == 0) {
        return 0;
    }

    int odd = 3;
    while (odd * odd <= n) {
        if (n % odd == 0) {
            return 0;
        }
        odd += 2;
    }
    return 1;
}