Thuật toán kiểm tra số nguyên tố nhanh nhất & cách lưu mảng 1 tỷ phần tử

Kien_Le2 · December 2, 2018, 12:27am

Mọi người ai có thuật toán kiểm tra số nguyên tố nào nhanh cho em xin đuoc không ạ,
Và mn cho hỏi cách lưu mảng một tỷ phần tử trong C++
Em cảm ơn ạ

noz1995 · December 1, 2018, 3:26pm

1 tỷ phần tử?
Giả sử bạn sử dụng kiểu int (4 bytes)
1 tỷ phần tử sẽ tiêu tốn của bạn gần 4GB bộ nhớ.

Bạn nghĩ bạn có nên nạp hết vào 1 mảng không? Vì mảng lưu trên RAM đó.

tntxtnt · December 1, 2018, 3:31pm

lưu mảng 1 tỷ phần tử làm gì? :V Cách dễ nhất là ra ngoài mua cây RAM 8GB về gắn vô máy là xong

1 tỷ phần tử kiểu bool thì có thể xài vector<bool> nó lưu chỉ có 128MB thôi

hoặc có thể mở 1 file lên đọc ghi theo binary, rồi chép 4GB xuống ổ cứng, truy cập từng phần tử bằng seek

Kien_Le2 · December 1, 2018, 3:36pm

Mình lưu vào file txt được không nhỉ, mình lưu mảng số nguyên tố tới 10 tỷ

tntxtnt · December 1, 2018, 3:54pm

số số ng tố bé hơn 10 tỷ có lẽ vào khoảng 50 triệu số thôi cần gì lưu tới 10 tỷ :V Hay là tìm 10 tỷ số ng tố đầu tiên à?

noname00 · December 1, 2018, 3:57pm

Chắc là bạn đang làm bài yêu cầu kiểm tra số nguyên tố (có thể lên đến số nguyên tố thứ 1 tỷ) lại tưởng là nhét vào mảng nên mới nghĩ như vậy

Càng những bài như vậy lại càng có cách làm khó hơn chứ không ai chơi mảng lưu trâu đâu

Kien_Le2 · December 1, 2018, 4:57pm

đúng rồi, mình đang làm tìm số nguyên tố đối xứng , số nguyên tố không thì sàng nguyên tố đơn giản hơn.

noname00 · December 1, 2018, 5:03pm

Dãy số nguyên tố đối xứng của bạn đây: https://oeis.org/A002385/b002385.txt. Không biết có đáp ứng được limit của đề không

Kiểm tra nguyên tố có thể dùng Miller - Rabin.

tntxtnt · December 1, 2018, 5:12pm

vì nó đối xứng nên cắt đôi nó ra, ví dụ tới 10 tỷ thì chỉ chạy i tới 10^5 là được, đảo i rồi ráp lại và có thể thêm số 0-9 ở giữa nữa là ra số đối xứng, sau đó mới đi kiểm tra tính nguyên tố của số này, kiểm tra bằng cách thường chạy tới căn(n) cũng được :V

Phong_Ky_Vo · December 2, 2018, 2:08am

Hi Kien Le.
Theo mình thì kiểm tra tới 1 tỉ thì cũng chỉ có 6e6 số nguyên tố nếu giá trị lưu trong biến int không dấu thì vẫn đủ khi đó cần 1 mảng kích thước 30M. Khi bạn đã lưu lại các số nguyên tố rồi thì thuật toán kiểm tra số nguyên tố rất nhanh.

#1 Sau 25p chạy thì mới đến có 12901799 chắc phải code đa luồng mất.

rogp10 · December 2, 2018, 2:09am

2 tỉ trở lên thì chia thử đến 301 + quay RM 7 vòng là nhanh gấp 5 lần

Kien_Le2 · December 2, 2018, 2:32am

cảm ơn HK boy ạ , nhưng em kiểm tra số nguyên tố đối xứng là tổng (số nt trước + số nt sau)/2 = snt ạ. vd như( 3 + 7 )/2 =5 cũng là số nguyên tố

rogp10 · December 2, 2018, 2:35am

Cái này gọi là cấp số cộng nguyên tố rồi bạn

tntxtnt · December 2, 2018, 2:44am

1 giây tính ra cái list A002385 kia

#include <algorithm>
#include <boost/multiprecision/cpp_int.hpp>
#include <cstdint>
#include <iostream>
#include <vector>

namespace impl
{
    template <class Uint1, class Uint2>
    Uint1 mulm(Uint1 a, Uint1 b, Uint1 m) // a * b (mod m)
    {
        return static_cast<Uint1>(static_cast<Uint2>(a) * b % m);
    }
    template <class Uint1, class Uint2>
    Uint1 powm(Uint1 a, Uint1 e, Uint1 m) // a^e (mod m)
    {
        Uint1 r = 1;
        for (; e; e /= 2, a = mulm<Uint1, Uint2>(a, a, m))
            if (e % 2) r = mulm<Uint1, Uint2>(r, a, m);
        return r;
    }
    template <class Uint1, class Uint2>
    bool millerRabinWitness(Uint1 a, Uint1 s, Uint1 d, Uint1 n)
    {
        if ((a = powm<Uint1, Uint2>(a, d, n)) == 1) return true;
        for (; s--; a = mulm<Uint1, Uint2>(a, a, n))
            if (a == n - 1) return true;
        return false;
    }
} // namespace impl

template <class Uint1, class Uint2, Uint1... AList>
struct DetMillerRabin {
    Uint1 aList[sizeof...(AList)]{std::forward<Uint1>(AList)...};
    bool operator()(Uint1 n)
    {
        if (n < 2) return false;
        // write n-1 as 2^s * d by factoring powers of 2 from n-1
        Uint1 s = 0, d = n - 1;
        while (d % 2 == 0) d /= 2, ++s;
        // witness loop
        return std::all_of(std::begin(aList), std::end(aList), [&](Uint1 a) {
            if (a > n - 2 || a < 2) return true; // ignore a outside of [2, n-2]
            return impl::millerRabinWitness<Uint1, Uint2>(a, s, d, n);
        });
    }
};

template <class Uint>
bool checkSmallFactors(Uint n)
{
    static const Uint smallFactors[] = {
        2u,   3u,   5u,   7u,   11u,  13u,  17u,  19u,  23u,  29u,
        31u,  37u,  41u,  43u,  47u,  53u,  59u,  61u,  67u,  71u,
        73u,  79u,  83u,  89u,  97u,  101u, 103u, 107u, 109u, 113u,
        127u, 131u, 137u, 139u, 149u, 151u, 157u, 163u, 167u, 173u,
        179u, 181u, 191u, 193u, 197u, 199u, 211u, 223u, 227u};
    return std::all_of(std::begin(smallFactors), std::end(smallFactors),
                       [&](Uint f) { return n == f || n % f; });
}

template <class Func>
void forEachPalindromeNumber(uint64_t p, Func&& yield) // Pythonic name `yield`
{
    uint64_t q = 0, t = 1;
    for (uint64_t i = p; i; i /= 10, t *= 10) q = q * 10 + i % 10;
    yield(p * t + q); // pq
    p *= 10 * t;
    for (uint64_t d = 0; d < 10; ++d) // p[0-9]q
        yield(p + d * t + q);
}

int main()
{
    using uint128_t = boost::multiprecision::uint128_t; // or unsigned __int128
    DetMillerRabin<uint64_t, uint128_t, 2, 13, 23, 1662803> isPrimeLt1e12;
    std::vector<uint64_t> palinPrimes; // palindromic primes
    for (uint64_t i = 0; i < 100000; ++i)
        forEachPalindromeNumber(i, [&](uint64_t n) {
            if (checkSmallFactors(n) && isPrimeLt1e12(n))
                palinPrimes.push_back(n);
        });
    std::sort(begin(palinPrimes), end(palinPrimes));

    for (int i = 0; i < 100; ++i)
        std::cout << i + 1 << " " << palinPrimes[i] << "\n";
    std::cout << palinPrimes.size() << " " << end(palinPrimes)[-1] << "\n";
}