本文介绍了在给定的范围内的质数的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

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

 #包括< stdio.h中>
#包括< MATH.H>

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

 对于(i = 0; I< = N-M + 2;我++)
 S [I] = 0;

 如果(M%2 == 0)
     I =米;

 其他 {
   I = m + 1个;

      }

 对于(; I< = N,I + = 2){
       S [I-米] = 1;

            }


 对于(i = 3; I< = X,I + = 2){

     如果(I> = M&功放;&放大器; S [I-M])继续;

    如果(I * I> = M)J = I * I;
     其他 {
     一个=(M-I * I)%(2 *ⅰ);
      若(a == 0),J =米;
       其他
      J = M +(2 * I-A);
    }
     对于(; J< = N; J + = 2 * I){

            S [J-M] = 1;
              }
   }

 如果(米== 1)I = 1;否则I = 0;
 对于(; I< = N-M;我++)

     如果(!S [I]){


       的printf(%LLD \ N,我+ M);
       }


}







  诠释的main(){
  INT吨;
  得到long long int M,N;
  scanf函数(%D \ N,& T公司);
  而(T  - ){
      scanf函数(%LLD%法学博士,与安培;男,&安培; N);

      筛(M,N);
      的printf(\ N);
         }

    回报(0);





   }
 

解决方案

 如果(M%2 == 0)
    I =米;
其他 {
    I = m + 1个;
}
对于(; I< = N,I + = 2){
    S [I-米] = 1;
}
 

现在,会发生什么,如果 M< = 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?

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

07-11 17:06