Работа с праймориалами. Поиск n-ого члена праймориала

Question

Нам дана разность двух праймориалов (это произведение простых чисел) p_a# и p_b#. Нужно найти а-ый и b-ый члены соответствующих праймориалов. Гарантируется, что X (разность праймориалов) меньше 10^18.Пример: разность--30000, искомые величины-- 13 и 5.

Я сам пробовал решить, но не получилось. Вот что вышло:

#include <iostream>
using namespace std;

bool isPrime(int num) {
if (num < 2)
    return false;

for (int i = 2; i <= num / 2; i++) {
    if (num % i == 0)
        return false;
}

return true;
}

bool isPrimorial(int n) {
int prime = 2;
int product = 1;

while (product <= n) {
    bool isPrime = true;
    for (int i = 2; i <= sqrt(prime); i++) {
        if (prime % i == 0) {
            isPrime = false;
            break;
        }
    }
    if (isPrime) {
        product *= prime;
        if (product == n) {
            return true;
        }
    }
    prime++;
}

return false;
}

long long NumberFromPrimorial(int primorial) {
long long number = primorial;
int counter = 1;
for (int i = 2; i <= primorial; i++) {
    if (isPrime(i)) {
        number /= i;
        counter++;
    }
    if (!isPrime(i)) {
        counter++;
        continue;
    }
    if (number == 1) {
        break;
    }
}
return counter;
}

int main() {
long long dif, num1 = 1, num2 = 1;
int counter1 = 1, counter2 = 1, i = 2;
cin >> dif;
for(long long it = 2;it>0;it++){
    if (isPrimorial(it) && isPrimorial(dif + it)) {
        cout << NumberFromPrimorial(dif + it) << " " << NumberFromPrimorial(it) << endl;
        break;
    }
}
return 0;

} Из 50 тестов проходит только 7, а остальные -- TLE.

Answer 1

Так что... делим разность на 2, 3, 5..., пока делится — так находим b. Дальше увеличиваем на 1 и продолжаем в том же духе, пока не доберемся до a. Ну, что-то такое:

#include <iostream>

using namespace std;

int primes[15] = { 2,  3,  5,  7, 11, 13, 17, 
                  19, 23, 29, 31, 37, 41, 43, 47, 53, 59 }; // Хватит за глаза...


int main(int argc, char * argv[])
{
    unsigned long long a, b, N;

    cin >> N;
    for(b = 0; N%primes[b] == 0; N/= primes[b++]);

    cout << "b = " << primes[b-1] << endl;

    N++;

    for(a = b; N%primes[a] == 0; N/= primes[a++]);

    cout << "a = " << primes[a-1] << endl;

}

Перебор — очень, очень плохая идея, тем более до 10¹⁸...

P.S. Никаких проверок потому, что считаем, что это число и в самом деле разность двух праймориалов...

Answer 2

Ввиду крохотной размерности задачи можно просто сохранить примориалы в таблице и искать подходящую разность (всего ~200 операций), либо сохранить разности (при большом количестве запросов)

#include <iostream>
#include <map>
#include <vector>
using namespace std;


int main()
{
    map<long long, pair<int, int>> table;
    int primes[15] = { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 };
    long long pt[15];
    pt[0] = 2;
    for (int i = 1; i < 15; i++)
        pt[i] = pt[i-1] * primes[i];
    for (int i = 0; i < 14; i++)
        for (int j = i + 1; j < 15; j++)
            table.insert(make_pair(pt[j] - pt[i], make_pair(primes[i], primes[j])));
    pair<int, int > p = table[30000];
    cout << p.first << " " << p.second<<"\n";
    p = table[614882361850356600];
    cout << p.first << " " << p.second;
}

    5 13
    37 47

БЛОГ НА HUSL

Работа с праймориалами. Поиск n-ого члена праймориала

Ответы (2 шт):