在给定的范围内的质数 [英] prime numbers in a given range

问题描述

我要找到两个数m和n之间的所有质数。 （1＆LT; = M＆LT; = N＆LT; = 10亿和纳米＆LT; = 100000）。我用的筛埃拉托色尼的，但得到错误的答案。谁能帮我什么是错我的code。

 ＃包括＆LT; stdio.h中＆GT;
＃包括＆LT; MATH.H＆GT;

INT S [100002]。
无效筛（长的长整型男，得到long long int n）的
{
 得到long long int x =开方（N）;
长长的INT I，J;
长长的诠释一个;

 对于（i = 0; I＆LT; = N-M + 2;我++）
 S [I] = 0;

 如果（M％2 == 0）
     I =米;

 其他 {
   I = m + 1个;

      }

 对于（; I＆LT; = N，I + = 2）{
       S [I-米] = 1;

            }


 对于（i = 3; I＆LT; = X，I + = 2）{

     如果（I＆GT; = M＆功放;＆放大器; S [I-M]）继续;

    如果（I * I＆GT; = M）J = I * I;
     其他 {
     一个=（M-I * I）％（2 *ⅰ）;
      若（a == 0），J =米;
       其他
      J = M +（2 * I-A）;
    }
     对于（; J＆LT; = N; J + = 2 * I）{

            S [J-M] = 1;
              }
   }

 如果（米== 1）I = 1;否则I = 0;
 对于（; I＆LT; = N-M;我++）

     如果（！S [I]）{


       的printf（％LLD \ N，我+ M）;
       }


}







  诠释的main（）{
  INT吨;
  得到long long int M，N;
  scanf函数（％D \ N，＆amp; T公司）;
  而（T  - ）{
      scanf函数（％LLD％法学博士，与安培;男，＆安培; N）;

      筛（M，N）;
      的printf（\ N）;
         }

    回报（0）;





   }
 

解决方案

 如果（M％2 == 0）
    I =米;
其他 {
    I = m + 1个;
}
对于（; I＆LT; = N，I + = 2）{
    S [I-米] = 1;
}
 

现在，会发生什么，如果 M＆LT; = 2 ？将2被认为主要还是不是？

I have to find all the prime numbers between two numbers m and n. (1 <= m <= n <= 1000000000 and n-m <= 100000). I am using sieve of eratosthenes but getting wrong answer. Can anyone help me what is wrong with my code.

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





   }

解决方案

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

Now, what happens if m <= 2? Will 2 be considered prime or not?

这篇关于在给定的范围内的质数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！