c - 与えられた範囲の素数

Question

2つの数mとnの間のすべての素数を見つけなければなりません。（1 <= m <= n<=1000000000およびnm<=100000）。エラトステネスのふるいを使用していますが、間違った答えが返ってきます。誰かが私のコードの何が悪いのか私を助けてくれますか？

#include<stdio.h>
#include<math.h>

int S[100002];
void sieve(long long int m, long long int n)
{
 long long int x=sqrt(n);
long long  int i,j;
long long int a;

 for(i=0;i<=n-m+2;i++)
 S[i]=0;

 if(m%2==0)
     i=m; 

 else {
   i=m+1;

      }

 for (;i<=n;i+=2){
       S[i-m]=1;

            }


 for (i=3;i<=x;i+=2){

     if(i>=m && S[i-m]) continue;

    if(i*i>=m)j=i*i;
     else {
     a = (m-i*i)%(2*i);
      if(a==0)j=m;
       else 
      j=m+ (2*i -a);
    }
     for (;j<=n;j+=2*i){

            S[j-m]=1;
              }
   }

 if (m==1)i=1; else i=0;
 for (;i<=n-m;i++)

     if (!S[i]){


       printf("%lld\n",i+m);
       }


}







  int main(){
  int t;
  long long int m,n;
  scanf("%d\n",&t);
  while(t--){
      scanf("%lld %lld",&m,&n);

      sieve(m,n);
      printf("\n");
         }

    return(0);                         





   }

Answer 1

if(m%2==0)
    i=m; 
else {
    i=m+1;
}
for (;i<=n;i+=2){
    S[i-m]=1;
}

では、次の場合はどうなりm <= 2ますか? 2 は素数と見なされますか?

Answer 2

メインでループを使用し、プライム関数を呼び出す必要があります。sqrt 関数は多くの CPU クロックを必要とするため、パフォーマンスのために使用しないことをお勧めします。

bool isPrime(int number){

    if(number < 2) return false;
    if(number == 2) return true;
    if(number % 2 == 0) return false;
    for(int i=3; (i*i)<=number; i+=2){
        if(number % i == 0 ) return false;
    }
    return true;

}

***数値の範囲のデータ型を変更します (long、long long など)。

Answer 3

範囲内の素数を見つけるのに最も効率的な (ふるい法) 方法です。ここで 1 は従来のように素数とは見なされません。

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

#define max 10000000

using namespace std;

int main()
{
    unsigned long long int  i, j, k, m, n;
    unsigned long long int* a = new unsigned long long int[max];

    scanf("%ul %ul",&m,&n);
   for(i = 1;i<=n;i++)
     a[i]=i;
   a[1] = 0;
   for(i=2;(i*i)<=n;i++)
    if(a[i]!=0)
      for(k=2*i;k<=n;k=k+i)
        if(a[k]!=0)
          a[k]=0;

    for(i =m;i<=n;i++)
        if(a[i]!=0) 
          printf("%ul ",a[i]);

    memset(a, 0, sizeof(a));
    return 0;
}