0

Digressing a bit on the site I came across this question, It is clear to me that generating prime numbers is complicated and some of the solutions given in that question to make the problem easier are good and ingenious, It occurs to me that perhaps giving the program some leading digits for large primes will make the search easier, is this correct? For example, perhaps finding 10-digit primes starting with 111 is easier than generating all 10-digit primes (even the more leading digits provided this makes it less complex).

Searching on the net (I must clarify that I am not a mathematician and I am not a computer scientist) I found the following code to generate primes of n digits

#include <bits/stdc++.h>

using namespace std;
const int sz = 1e5;
bool isPrime[sz + 1];

// Function for Sieve of Eratosthenes

void sieve() {
    memset(isPrime, true, sizeof(isPrime));
    isPrime[0] = isPrime[1] = false;
    for (int i = 2; i * i <= sz; i++) {
        if (isPrime[i]) {
            for (int j = i * i; j < sz; j += i) {
                isPrime[j] = false;
            }
        }
    }
}

// Function to print all the prime

// numbers with d digits

void findPrimesD(int d) {
    // Range to check integers
    int left = pow(10, d - 1);
    int right = pow(10, d) - 1;
    // For every integer in the range
    for (int i = left; i <= right; i++) {
        // If the current integer is prime
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
}

// Driver code

int main() {
    // Generate primes
    sieve();
    int d = 1;
    findPrimesD(d);
    return 0;
}

My question is, how to take advantage of this code to give it the first m digits and thus make the search easier and smaller?

President James K. Polk
  • 40,516
  • 21
  • 95
  • 125
user19872448
  • 25
  • 3
  • 1
    Having back-ticks around each line makes it look like that. Better to simply paste the code, highlight the entire thing, and hit `ctrl+k`. Finding a genuinely large prime (of the type useful in cryptography) is unlikely to be sped-up meaningfully by deciding on a prefix. You would just be decreasing the security for no good reason. – John Coleman Dec 12 '22 at 23:52
  • 2
    Finding large primes can be done very efficiently by choosing a random very large odd number (last bit is a 1) and testing if it is prime with (say) Miller-Rabin. Repeat until a prime is found. Here's a discussion of that you may find straighforward enough for your taste. https://ghenshaw-work.medium.com/finding-large-primes-for-public-key-cryptography-9c5a5c0d32c4 – Sturt Dec 12 '22 at 23:58
  • 2
    *...For example, perhaps finding 10-digit primes starting with 111 is easier than generating all 10-digit primes...* Yes, of course it is, because the range to check is 1000 times smaller. But as far as I know there's no magic prefix of digits that has significantly more primes than any other prefix, assuming we're disallowing leading zeros. Smaller numbers are more likely to be prime, so 111 will do a little bit better than 999, but that effect gets smaller as the number of digits gets larger. – President James K. Polk Dec 13 '22 at 01:41
  • @PresidentJamesK.Polk Having said the above, do you know if there is any code on the net that already does this job? – user19872448 Dec 13 '22 at 02:24
  • 1
    Asking for off-site resources makes your question off-topic. – President James K. Polk Dec 13 '22 at 02:25
  • @PresidentJamesK.Polk I understand, so it would be worth asking for a hint to take advantage of the code provided in the question? – user19872448 Dec 13 '22 at 02:30
  • user19872448, note: `i * i <= sz` risks overflow when `sz` near `INT_MAX`. `i <= sz/i` functions the same and does not overflow. – chux - Reinstate Monica Dec 14 '22 at 10:55
  • It is unclear if the goal is to find a prime or all the primes in the select range. – chux - Reinstate Monica Dec 14 '22 at 11:02
  • 1
    I don't know about *better* prefixes, but there are certainly some *worse* prefixes to avoid, which will produce more semiprimes with only two large prime factors (which will evade trial division pruning). If you find a prefix that tends to produce more B-smooth numbers, your primality testing may become easier on average (possibly at the cost of less overall primes on average). Just a thought – Dillon Davis Dec 15 '22 at 07:25
  • Do you require a C++ program to generate an n-digit prime number containing specified prefix digits at the start of the prime number? like a 10-digit prime number that has "111" as a prefix at the beginning of that 10-digit prime number, between the range 1110000000 to 1119999999, like 1110000019, 1110000049 ... so on? – FAQi Jul 17 '23 at 07:39

0 Answers0