-3

我必须找到两个数 m 和 n 之间的所有质数。（1 <= m <= n <= 1000000000 和 nm <= 100000）。我正在使用 Eratosthenes 筛但得到错误的答案。谁能帮我我的代码有什么问题。

#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);                         





   }
4

4 回答 4

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

现在，如果 会发生什么m <= 2？2 是否会被视为素数？

于 2013-01-07T16:37:50.497 回答
0

您应该在 main 中使用循环并调用主要函数。出于性能考虑，我建议您避免使用 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 等）。

于 2013-01-19T20:18:21.730 回答
0

这是查找范围之间的素数的最有效（筛法）方法。这里 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;
}
于 2013-11-13T19:56:05.080 回答
0 
#include<stdio.h>
#include<stdlib.h>
void prime(int ); 

int main(){
int x,  end;
    printf("Enter end of the range:\n");
    scanf("%d", &end);

    for(x = 2;x <= end;x++){
        prime(x);
    }   
    return 0;
}

void prime(int x){
    int j, count = 1;
    for(j=2;j <= x;j++){
        if(x % j == 0){
            count += 1;
            //printf("count = %d,x = %d", count, x);
        }
    }
    if(count == 2){
        printf("\n%d\n", x);
    }
}
于 2016-07-30T06:01:14.127 回答