1 
#include<iostream>
#include<string.h>
#include<math.h>
using namespace std;    

bool prime[1000000500];
void generate(long long end)
{
    memset(prime,true,sizeof(prime));
    prime[0]=false;
    prime[1]=false;

        for(long long i=0;i<=sqrt(end);i++)
        {
         if(prime[i]==true)
         {
             for(long long y=i*i;y<=end;y+=i)
             {
                 prime[y]=false;
             }
         }
        }
}

int main()
{
    int n;
    long long b,e;
    scanf("%d",&n);
    while(n--)
    {
        cin>>b>>e;
        generate(e);
        for(int i=b;i<e;i++)
        {
            if(prime[i])
                printf("%d\n",i);
        }
    }
    return 0;
}

那是我的 spoj prime 生成器代码。
尽管它会生成与另一个接受的代码相同的输出..

4

7 回答 7

2

您不需要筛选每个数字直到最后一个数字。这很愚蠢。只对开始和结束数字之间的范围进行操作。（部分筛子）

我已经在 Python 中解决了这个问题，这就是我最终设法做到的方式。我还开始计算所有素数，直到潜在最大值的平方根 1000000000。这只是 31623，所以不需要很长时间。

从此列表中使用这些数字直到当前案例最大值的平方根来筛选当前案例。

于 2010-01-19T02:27:56.967 回答
2

这个问题需要一个分段筛实现。一个简单的 Eratosthenes 分段筛可以很容易地用 C/C++ 用大约 50-60 行代码进行编程。如果您实现分段筛，则只需为问题中提到的最大大小的段分配内存。

还有一些其他的优化可以提供一些帮助。我将列出我在解决方案中所做的：

  • 检查只有素数的倍数，直到最大数的平方根。

  • 所有素数的查找数组直到最大可能数的平方根，即 sqrt(10^9) 可以预先计算并添加到源代码中。此问题的 SPOJ 源代码大小限制为 50000 字节，添加此查找数组仍符合此大小限制。

  • 划掉倍数时，从 y=i*i 开始，但只检查 i 的奇数倍。

通过这些优化，我的 C++ 代码在大约 0.05 秒内运行。即使没有这些优化，我认为分段筛也应该被接受。希望这可以帮助。

于 2011-12-15T18:15:58.637 回答
1

一个让它更快的简单技巧是sqrt从 for 循环中取出：

double sqrtOfEnd = sqrt(end);
for(long long i=0; i<=sqrtOfEnd; i++)
{
  ...

您不需要在每个循环上重新计算平方根。
正如其他人指出的那样，这可能还不够，您可能不得不考虑其他寻找素数的方法。

于 2010-01-15T08:40:11.300 回答
1

由于您需要从多个序列中输出素数，可能会保留先前筛分的结果，只根据需要继续填写表格的其余部分？

于 2010-01-15T09:07:06.907 回答
0

You need to make it faster - for test cases such as the range 999900000-1000000000, Eratosthene's sieve algorithm is too slow. There are other alternatives you could try and will yield better results.

PS. Of course I won't tell you which these are. Do your homework. :P

于 2010-01-15T07:59:04.473 回答
0

@nakedfantaic 没错！

#include <cstdio>
#include <cmath>

unsigned int numbers[3500], len;

inline bool prime(unsigned int x)
{
    unsigned int i, last = sqrt(x);
    for (i = 2; i <= last; i++) {
        if (!(x % i)) {
            return 0;
        }
    }
    return 1;
}

void generate()
{
    for (unsigned int i = 2; i < 32000; i++) {
        if (prime(i)) {
            numbers[len++] = i;
        }
    }
}

inline bool process(unsigned long x)
{
    unsigned int i, last = sqrt(x);
    for (i = 0; i < len && numbers[i] <= last; i++) {
        if (!(x % numbers[i])) {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int tests;
    unsigned long begin, end;
    generate();
    scanf("%d", &tests);
    while (tests-- > 0) {
        scanf("%u %u", &begin, &end);
        if (begin == 1) {
            begin++;
        }
        while (begin <= end) {
            if (process(begin)) {
                printf("%u\n", begin);
            }
            begin++;
        }
        printf("\n");
    }
    return 0;
}

http://pastebin.com/G5ZRd5vH

于 2011-03-06T13:30:02.690 回答
0

我可以帮助使用 python 3.4，我的 spoj(prime generator) 工作代码是这样的：

import math
primes = [True for i in range(int(math.sqrt(1000000000))+1)]
tes = int(math.sqrt(math.sqrt(1000000000)*2))+1
for i in range(2,tes):
    if primes[i]:
        for z in range(i*i,int(math.sqrt(1000000000))+1,i):
            primes[z] = False
for z in range(int(input().strip())):
    m,n = map(int,input().strip().split())
    if n == 1:
        print('')
        continue
    elif m == 1:
        m += 1
    ans = [True for i in range(n-m+1)]
    for i in range(2,int(math.sqrt(1000000000))+1):
        if primes[i]:
            if i > n:
                break
            num = m//i
            if num*i != m:
                num += 1
            if num < 2:
                num = 2
            while num*i <= n:
                ans[num*i-m] = False
                num += 1
    for i in range(n-m+1):
        if ans[i]:
            print(i+m)
    print('')
于 2016-12-12T11:02:10.810 回答