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素数ジェネレーターの私のコードです。
Altoughtは、別の受け入れられたコードと同じ出力を生成します。

4

7 に答える 7

2

この問題には、Segmented Sieve の実装が必要です。シンプルなセグメント化されたエラトステネスのふるいは、C/C++ で約 50 ～ 60 行のコードで簡単にプログラムできます。セグメント化されたふるいを実装する場合は、問題で言及されている最大サイズのセグメントにのみメモリを割り当てる必要があります。

少し役立つ他の最適化がいくつかあります。私のソリューションで行ったものをリストします。

  • 最大数の平方根までの素数のみの倍数をチェックします。

  • 可能な最大数の平方根、つまり sqrt(10^9) までのすべての素数のルックアップ配列を事前に計算して、ソース コードに追加することができます。この問題に対する SPOJ ソース コードのサイズ制限は 50000 バイトであり、このルックアップ配列を追加しても、このサイズ制限内に収まります。

  • 倍数を消すときは、y=i*i から始めますが、i の奇数倍だけをチェックします。

これらの最適化により、私の C++ のコードは約 0.05 秒で実行されました。これらの最適化がなくても、セグメント化されたふるいが受け入れられるべきだと思います。お役に立てれば。

于 2011-12-15T18:15:58.637 に答える
2

最後の数字まですべての数字をふるいにかける必要はありません。それはばかげています。開始番号と終了番号の間の範囲のみを操作します。（部分ふるい）

私はこの問題を Python で解決しましたが、それが最終的に解決した方法です。また、潜在的な最大値 1000000000 の平方根までのすべての素数を計算することから始めました。これはわずか 31623 であるため、それほど時間はかかりません。

このリストから、現在のケースの最大値の平方根までの数値を使用して、現在のケースをふるいにかけます。

于 2010-01-19T02:27:56.967 に答える
1

多数のシーケンスから素数を出力する必要があるため、以前のふるい分けの結果を保持し、必要に応じてテーブルの残りの部分のみを入力し続けることができますか?

于 2010-01-15T09:07:06.907 に答える
1

sqrt高速化する簡単な方法は、for ループから抜け出すことです。

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

ループごとに平方根を再計算する必要はありません。
他の人が指摘したように、これは十分ではない可能性があり、素数を見つける他の方法を検討する必要があるかもしれません.

于 2010-01-15T08:40:11.300 に答える
0

より速くする必要があります - 範囲 999900000-1000000000 などのテスト ケースでは、Eratosthene のふるいアルゴリズムは遅すぎます。あなたが試すことができる他の選択肢があり、より良い結果が得られます.

PS。もちろん、これらがどれであるかは教えません。宿題をしなさい。:P

于 2010-01-15T07:59:04.473 に答える
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 に答える
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 に答える