Prime Generator算法-Java 学习之路

我一直在努力解决素数生成器算法的SPOJ问题 .

这是问题所在

彼得想为他的密码系统生成一些素数 . 帮助他！您的任务是生成两个给定数字之间的所有素数！输入输入以单行中的测试用例数t开始（t <= 10） . 在接下来的t行中的每一行中，存在由空格分隔的两个数m和n（1 <= m <= n <= 1000000000，n-m <= 100000） . 输出对于每个测试用例，打印所有质数p，使得m <= p <= n，每行一个数，测试用例用空行分隔 .

这很容易，但在线判断显示错误，我没有得到“测试用例”的问题，以及为什么要使用1000000范围 .

这是我的代码 .

#include<stdio.h>

main()
{
int i, num1, num2, j;
int div = 0;
scanf("%d %d", &num1, &num2);
for(i=num1; i<=num2; i++)
  {
    for(j=1; j<=i; j++)
    {
      if(i%j == 0)
      {
        div++;
      }
    }
    if(div == 2)
    {
     printf("%d\n", i);
    }
    div = 0;
  }
  return 0;
}

8 回答

1
我无法评论alogirthm以及100000数字范围是否允许优化，但是代码无效的原因是因为它似乎没有正确解析输入 . 输入将是这样的：
```
2
123123123 123173123 
987654321 987653321
```
这是第一行将给出每行输入的输入组数，然后是一组输入 . 你的程序一目了然，看起来只是在读第一行寻找两个数字 .

我假设在线判断只是在寻找正确的输出（可能是合理的运行时间？），所以如果你纠正了写入输入，无论你的算法效率如何（正如其他人已开始评论），它应该可以工作 .
回复于 2024-04-20T07:49:50+08:00
0
要在 m,n 1 <= m <= n <= 1000000000, n-m<=100000 之间找到素数，首先需要准备从2到 sqrt(1000000000) < 32000 的核心素数 . 简单的连续sieve of Eratosthenes绰绰有余 . （筛选了核心bool sieve []数组（相关的C代码在这里），做一个单独的数组int core_primes []包含核心素数，从筛子数组中浓缩，以易于使用的形式，因为你有更多比他们筛选的一个偏移部分 . ）

然后，对于每个给定的单独段，只需使用准备好的核心质粒筛分它 . 100,000足够短，没有平均值，只有50,000赔率 . 您可以使用一个预先分配的数组，并为每个新对调整寻址方案 m,n . 数组中的 i -th条目将表示数字 o + 2i ，其中 o 是给定段的奇数开始 .

也可以看看：
关于术语的一句话：这不是“分段筛” . 这指的是一个接一个地对连续的段进行筛分，随着时间的推移更新核心质数列表 . 这里的上限是事先已知的，其平方根非常小 .

相同的核心质数用于筛分每个单独的偏移段，因此可以更好地描述为Eratosthenes的筛子 . 对于每个被筛分的区段，当然只需要使用不大于其上限的平方根的核心素数;但核心质数不会更新，而每个这样的偏移段都被筛选（更新核心质数是"segmented"筛子的特征） .
回复于 2024-04-20T07:49:50+08:00
0

你的上限是10 ^ 9 . Eratosthenes的筛子是 O(N loglogN) ，这对于那个界限太大了 .

以下是一些想法：

更快的素性测试

循环范围[i，j]并检查每个数字是否为素数的天真解决方案的问题是，如果处理多个案例，则需要 O(sqrt(N)) 来测试数字是否为素数过多 .

但是，您可以尝试更智能的素性测试算法 . Miller-Rabin是 N 的位数的多项式，并且对于N <= 10 ^ 9，您只需要检查a = 2,7和61 .

请注意，我实际上没有尝试过这个，所以我不能保证它会起作用 .

分段筛

正如@KaustavRay所提到的，你可以使用分段筛 . 根本的想法是，如果数字N是复合的，那么它具有最多为sqrt（N）的素数除数 .

我们使用Eratosthenes筛选算法找到低于32,000的素数（大致为sqrt（10 ^ 9）），然后对于[i，j]范围内的每个数字，检查是否有任何低于32,000的素数除以它 .

通过prime number theorem大约一个在log（N）中的数字是素数，它足够小以便在时间限制内挤压 .

回复于 2024-04-20T07:49:50+08:00
2
输入以单行中的测试用例数t开始（t <= 10），您的程序中没有测试用例 . 它错了，对不起我的英语
```
2 - //the number of test cases
1 10 - // numbers n,m
3 5 - // numbers
```
您的程序只能在第一行工作 .
回复于 2024-04-20T07:49:50+08:00

#include <stdio.h>
#include <math.h>
int main()
{
    int test;
    scanf("%d",&test);
    while(test--)
    {
        unsigned int low,high,i=0,j=2,k,x=0,y=0,z;
        unsigned long int a[200000],b[200000];
        scanf("%d",&low);
        scanf("%d",&high);
        for(i=low;i<=high;i++)
            a[x++]=i;
        for(i=2;i<=32000;i++)
            b[y++]=i;
        i=0;
        while(b[i]*b[i]<=high)
        {
            if(b[i]!=0)
            {
                k=i;
                for(;k<y;k+=j)
                {
                    if(k!=i)
                    {
                        b[k]=0;
                    }
                }
            }
            i+=1;j+=1;
        }
            for(i=0;i<y;i++)
            {
                if(b[i]!=0 && (b[i]>=low && b[i]<=sqrt(high)))
                    printf("%d\n",b[i]);
            }
            int c=0;
            for(i=0;i<y;i++)
            {
                if(b[i]!=0 && (b[i]>=1 && b[i]<=sqrt(high)))
                    b[c++]=b[i];
            }
            int m=a[0];
            for(i=0;i<c;i++)
            {
                z=(m/b[i])*b[i];k=z-m;
                if(k!=0)
                    k += b[i];
                for(;k<x;)
                {
                    if(a[k]!=0)
                    {
                        a[k]=0;
                    }
                    k+=b[i];
                }
            }
            for(i=0;i<x;i++)
            {
                if(a[i]!=0 && (a[i]>=2 && a[i]<=(high)))
                    printf("%d\n",a[i]);
            }
        printf("\n");
    }
    return 0;
}

回复于 2024-04-20T07:49:50+08:00

0

对于这么小的数字，您只需搜索1到1000000000之间的所有素数 .

拿62.5 mByte的RAM来创建一个二进制数组（每个奇数的一位，因为我们已经知道没有偶数（2除外）是素数） .

将所有位设置为0表示它们是素数，而不是使用Sieve of Eratosthenes将位设置为非素数的所有数中的1 .

筛选一次，存储结果列表 .

回复于 2024-04-20T07:49:50+08:00

int num; 
bool singleArray[100000]; 
static unsigned long allArray[1000000]; 
unsigned long nums[10][2]; 

unsigned long s;       
long n1, n2;
int count = 0; 
long intermediate; 


scanf("%d", &num);

for(int i = 0; i < num; ++i) 
{
    scanf("%lu", &n1);  
    scanf("%lu", &n2); 
    nums[i][0] = n1;   
    nums[i][1] = n2;   
}


for(int i = 0; i < 100000; ++i)  
{
    singleArray[i] = true;
}

for(int i = 0; i < num; ++i) 
{
    s = sqrt(nums[i][1]);
    for(unsigned long k = 2; k <= s; ++k)  
    {
        for (unsigned long j = nums[i][0]; j <= nums[i][1]; ++j) 
        {
            intermediate = j - nums[i][0];
            if(!singleArray[intermediate]) 
            {
                continue;
            }
            if((j % k == 0 && k != j) || (j == 1))      
            {
                singleArray[intermediate] = false;
            }
        }
    }


    for(unsigned long m = nums[i][0]; m <= nums[i][1]; ++m) 
    {
        intermediate = m - nums[i][0];
        if(singleArray[intermediate])  
        {
            allArray[count++] = m;
        }
    }

    for(int p = 0; p < (nums[i][1] - nums[i][0]); ++p)
    {
        singleArray[p] = true;
    }
 }


for(int n = 0; n < count; ++n)
{
    printf("%lu\n", allArray[n]);
}

}

回复于 2024-04-20T07:49:50+08:00

#include <iostream>
using namespace std;

int main() {

    // your code here
unsigned long int m,n,i,j;int N;
cin>>N;
for(;N>0;N--)
{
    cin>>m>>n;
    if(m<3)
        switch (n)
        {
            case 1: cout<<endl;continue;
            case 2: cout<<2<<endl;
                    continue;
            default:cout<<2<<endl;m=3;
        }
    if(m%2==0) m++;        
    for(i=m;i<=n;i+=2)
    {  
        for(j=3;j<=i/j;j+=2)
            if(i%j==0)
                {j=0;break;}
        if(j)
        cout<<i<<endl;
    }
        cout<<endl;

}return 0;}

回复于 2024-04-20T07:49:50+08:00

Prime Generator算法

8 回答

更快的素性测试

分段筛

相关问题