Можете ли вы сказать мне, почему это приводит к превышению лимита времени в спой (Генератор простых чисел) - PullRequest
Новая
       33

Можете ли вы сказать мне, почему это приводит к превышению лимита времени в спой (Генератор простых чисел)

1 голос
/ 15 января 2010 
#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;
}

Это мой код для генератора генерации спой.
Хотя он генерирует тот же вывод, что и другой принятый код ..

Ответы [ 7 ]

2 голосов
/ 15 декабря 2011

Эта проблема требует реализации Segmented Sieve. Простое сегментированное Сито Эратосфена может быть легко запрограммировано в C / C ++ примерно в 50-60 строк кода. Если вы внедрили сегментированное сито, вам нужно выделить память только для сегмента максимального размера, упомянутого в проблеме.

Есть несколько других оптимизаций, которые могут немного помочь. Я перечислю те, которые я сделал в моем решении:

  • Проверка на кратность только простых чисел вплоть до квадратного корня из максимального числа.

  • Массив поиска всех простых чисел до квадратного корня максимально возможного числа, т. Е. Sqrt (10 ^ 9), может быть предварительно рассчитан и добавлен в исходный код. Ограничение размера исходного кода SPOJ составляет 50000 байт для этой проблемы, и добавление этого поискового массива все еще вписывается в этот предел размера.

  • Вычеркивая кратные, начните с y = i * i, но отметьте только нечетные кратные i.

С этими оптимизациями мой код на C ++ работал примерно за 0,05 с. Даже без них оптимизация, я думаю, что сегментированное сито должно быть принято. Надеюсь, это поможет.

2 голосов
/ 19 января 2010

Вам не нужно просеивать каждое число до конечного числа. Это просто глупо. Работайте только в диапазоне между начальным и конечным числом. (Частичное сито)

Я решил эту проблему в Python, и мне, наконец, удалось это сделать. Я также начал с вычисления всех простых чисел вплоть до квадратного корня потенциального максимума 1000000000. Это всего 31623, поэтому это не займет много времени.

Из этого списка используйте эти числа вплоть до квадратного корня от максимума текущего случая, чтобы просеивать текущий случай.

1 голос
/ 15 января 2010

Так как вам нужно выводить простые числа из ряда последовательностей, возможно, вы будете следить за результатами предыдущих просеиваний и продолжать заполнять только остальную часть таблицы по мере необходимости?

1 голос
/ 15 января 2010

Простой способ сделать это быстрее - вытащить sqrt из цикла for: 

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

Вам не нужно пересчитывать квадратный корень в каждом цикле.
Как отмечают другие, этого может быть недостаточно, и вам, возможно, придется прибегнуть к другим методам поиска простых чисел.

0 голосов
/ 12 декабря 2016

Я могу помочь с Python 3.4, и мой рабочий код для spoj (основной генератор) выглядит так: 

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('')
0 голосов
/ 06 марта 2011

@ 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

0 голосов
/ 15 января 2010

Вам нужно сделать это быстрее - для тестовых случаев, таких как диапазон 999900000-1000000000, алгоритм сита Эратосфена слишком медленный. Есть и другие альтернативы, которые вы можете попробовать и которые принесут лучшие результаты.

PS. Конечно, я не скажу вам, что это. Делай свою домашнюю работу. : P

...