Как я могу улучшить свою программу простых чисел с помощью алгоритма Sieve of Eratosthenes?

Question

Моя программа печатает все простые числа из этого выражения:

((1 + sin(0.1*i))*k) + 1, i = 1, 2, ..., N.

Формат ввода:

Не более 100 примеров. Каждый пример имеет 2 натуральных числа в одной строке.

Формат вывода:

Вывести каждое число на отдельной строке.

Пример ввода:

4 10

500 100

Пример вывода:

5

17

Но мой алгоритм недостаточно эффективен. Как добавить сито эратосфена, чтобы оно было достаточно эффективным, чтобы не печатать «Прервано из-за тайм-аута».

#include <iostream>
#include <cmath>
using namespace std;

int main() {
long long k, n;
int j;
    while (cin >> k >> n) {
    if (n>1000 && k>1000000000000000000) continue;

    int count = 0;
    for (int i = 1; i <= n; i++) {
        int res = ((1 + sin(0.1*i)) * k) + 1;
        for (j = 2; j < res; j++) {
            if (res % j == 0) break;
        }
        if (j == res) count++;
    }
    cout << count << endl;

}
system("pause");

Answer 1

Когда вы используете простое Wheel factorization , вы можете получить очень хорошее ускорение вашего кода. Факторизация колеса порядка 2 использует тот факт, что все простые числа больше 3 можно записать как 6n + 1 или 6n + 5 для натуральных n . Это означает, что вам нужно сделать только 2 деления на 6 номеров. Или даже далее, все простые числа больше 5 могут быть записаны как 30n + m , с m в {1,7,11,13,17,19,23, 29} . (8 делений на 30 номеров).

Используя этот простой принцип, вы можете написать следующую функцию для проверки ваших простых чисел (колесо {2,3}):

bool isPrime(long long num) {
  if (num == 1)     return false;   // 1 is not prime
  if (num  < 4)     return true;    // 2 and 3 are prime
  if (num % 2 == 0) return false;   // divisible by 2
  if (num % 3 == 0) return false;   // divisible by 3
  int w = 5;
  while (w*w <= num) {
      if(num % w     == 0) return false; // not prime
      if(num % (w+2) == 0) return false; // not prime
      w += 6;
  }
  return true;                     // must be prime
}

Вы можете адаптировать вышеперечисленное для колеса {2,3,5}. Эта функция может использоваться в основной программе как:

int main() {
  long long k, n;

  while (cin >> k >> n) {
    if (n>1000 && k>1000000000000000000) continue;
    int count = 0;
    for (int i = 1; i <= n; i++) {
      long long res = ((1 + sin(0.1*i)) * k) + 1;
      if (isPrime(res)) { count++; }
    }
    cout << count << endl;
  }
  return 0;
}

Простое время дает мне исходный код (g++ prime.cpp)

 % time echo "6000 100000000" | ./a.out 
 12999811
 echo "6000 100000000"  0.00s user 0.00s system 48% cpu 0.002 total
 ./a.out  209.66s user 0.00s system 99% cpu 3:29.70 total

в то время как оптимизированная версия дает мне

% time echo "6000 100000000" | ./a.out                                                                                                                                                                                                        
12999811
echo "6000 100000000"  0.00s user 0.00s system 51% cpu 0.002 total
./a.out  10.12s user 0.00s system 99% cpu 10.124 total

Другие улучшения могут быть сделаны, но могут иметь незначительные эффекты:

1. предварительно вычисляет вашу таблицу синусов sin(0.1*i) для i от 0 до 1000. Это позволит избежать повторного вычисления этих синусов снова и снова. Это, однако, оказывает незначительное влияние, так как большая часть времени тратится на лучшие.
2. Проверка, если res(i) == res(i+1): это практически не влияет, поскольку, в зависимости от n и k большинство последовательных res не равны.
3. Используйте справочную таблицу, может быть удобнее, это действительно имеет значение.

оригинальный ответ:

Мое предложение следующее:

1. Предварительно вычислите ваш sinetable sin(0.1*i) для i от 0 до 1000. Это позволит избежать повторного вычисления этих синусов снова и снова. Также сделайте это умно (см. Пункт 3)
2. Найдите максимально возможное значение res, равное res_max=(2*k)+1

3. Найдите все простые числа для res_max, используя Сито Эратосфена . Также следует понимать, что все простые числа больше 3 можно записать как 6n + 1 или 6n + 5 для натуральных n . Или даже далее, все простые числа больше 5 могут быть записаны как 30n + m , с m в {1,7,11,13,17,19,23, 29} . Это то, что называется Факторизация колеса . Так что не стоит проверять любой другой номер. (чуть-чуть больше информации здесь )

4. Иметь справочную таблицу, в которой указано, является ли число простым числом.

5. Делайте все циклы над таблицей поиска.

Answer 2

Вы можете повысить свою скорость в 10 раз, просто выполняя работу с пробным отделением. Вы тестируете все целые числа от 2 до res, а не рассматриваете 2 как особый случай и тестируете только нечетные числа от 3 до квадратного корня из res:

// k <= 10^3, n <= 10^9

int main() {
    unsigned k;
    unsigned long long n;

    while (cin >> k >> n) {

        unsigned count = 0;

        for (unsigned long long i = 1; i <= n; i++) {
            unsigned long long j, res = (1 + sin(0.1 * i)) * k + 1;

            bool is_prime = true;

            if (res <= 2 || res % 2 == 0) {
                is_prime = (res == 2);
            } else {
                for (j = 3; j * j <= res; j += 2) {
                    if (res % j == 0) {
                        is_prime = false;
                        break;
                    }
                }
            }

            if (is_prime) {
                count++;
            }
        }

    cout << count << endl;
    }
}

Хотя k = 500 и n = 500000000 все равно потребуется сорок секунд или около того.

Answer 3

РЕДАКТИРОВАТЬ: я добавил третье средство для повышения эффективности
РЕДАКТИРОВАТЬ 2: Добавлено объяснение, почему сито не должно быть решением и некоторые отношения тригонометрии. Более того, я добавил примечание по истории вопроса

Ваша проблема не в том, чтобы сосчитать все простые числа в данном диапазоне, а только те, которые сгенерированы вашей функцией.

Поэтому я не думаю, что сито Эратосфена является решением для этого конкретного упражнения по следующей причине: n всегда довольно мало, а k может быть очень большим. Если k очень велико, то алгоритм Sieve должен будет генерировать огромное количество простых чисел, чтобы, наконец, использовать его для небольшого числа кандидатов.

Вы можете повысить эффективность своей программы тремя способами:

• Избегайте вычисления sin(.) каждый раз. Вы можете использовать тригонометрические отношения, например. Более того, при первом вычислении этих значений вы сохраняете их в массив и повторно используете эти значения. Расчет sin() очень трудоемкий
• В вашем тесте, чтобы проверить, является ли число простым, ограничьте поиск до sqrt(res). Кроме того, рассмотрите возможность проведения теста только с нечетным j, плюс 2
• Если кандидат res равен предыдущему, избегайте повторного выполнения теста

Немного тригонометрии
Если c = cos (0.1) и s = sin (0.1), вы можете использовать соотношения:

• sin (0.1(i+1)) = s*cos (0.1*i) + c*sin(0.1*i))
• cos (0.1(i+1)) = c*cos (0.1*i) - s*sin(0.1*i))

Если n было большим, необходимо регулярно пересчитывать sin() с помощью функции, чтобы избежать слишком большого вычисления ошибки округления. Но это не должно иметь место, поскольку n всегда довольно мало.

Однако, как я уже говорил, на первом этапе лучше использовать только трюк «запоминания» и проверить, достаточно ли этого.

Примечание к истории этого вопроса и почему этот ответ:

Недавно на этом сайте появилось несколько вопросов "как улучшить мою программу, чтобы подсчитать количество простых чисел, сгенерированных этой функцией k*sin() ..." Насколько мне известно, все эти вопросы были закрыты как дубликаты, по той причине, что Решето является решением и было объяснено в предыдущем аналогичном (но немного другом) вопросе. Теперь тот же вопрос появился в несколько иной форме: «Как я могу вставить алгоритм Sieve в эту программу ... (снова с помощью k * sin ())». И тогда я понял, что Сито не является решением. Это не критика предыдущих закрытий, поскольку я сделал ту же ошибку в понимании вопроса. Тем не менее, я думаю, что пришло время предложить новое решение, даже если оно не совсем соответствует новому вопросу