Подсчет простых чисел с помощью теста простоты AKS в C ++ Что я делаю не так? - PullRequest
Новая
       27

Подсчет простых чисел с помощью теста простоты AKS в C ++ Что я делаю не так?

0 голосов
/ 28 сентября 2018

Спокойной ночи, я не специалист по C ++.Мне нужно посчитать количество двойных простых чисел внутри 3 и предел.Мой вывод всегда дает 1. Что я делаю не так?Вот мой алгоритм работы AKS, а также!

#include <bits/stdc++.h>
using namespace std;

long long c[100];

void coef(int n)
{
    c[0] = 1;
    for (int i = 0; i < n; c[0] = -c[0], i++) {
        c[1 + i] = 1;

        for (int j = i; j > 0; j--)
            c[j] = c[j - 1] - c[j];
    }
}

bool isPrime(int n)
{

    coef(n);


    c[0]++, c[n]--;


    int i = n;
    while (i-- && c[i] % n == 0)
        ;


    return i < 0;
}

int main()
{
    int limit=10000,counter=1,i;
    for(i=3;i<=limit;i+=2){
    if (isPrime(i)){

        if(isPrime(i+2)){
                counter++;
    }
 }
}
cout <<counter;
return 0;
}

Я нахожусь на кодовых блоках 17.02 в Windows 10 Pro.Что за глупость я делаю?

1 Ответ

0 голосов
/ 09 октября 2018

Это не на все алгоритм AKS для простоты.Это выглядит как слегка измененная версия задачи RosettaCode , которая реализует экспоненциальную лемму времени.Это будет медленнее, чем простое пробное деление, не говоря уже о том, что без модульной арифметики эта реализация в принципе бесполезна, поскольку она будет переполнена при вводе данных даже игрушечного размера.не вызывайте isprime () для одних и тех же входов снова и снова.Вы можете звонить один раз на номер и просто запомнить последнее простое число, которое вы нашли.Если isprime (i) имеет значение true, подсчитайте, был ли последний найденный вами i-2.Теперь вам не нужны ни повторные вызовы, ни массив значений.

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

...