#include <iostream>
#include <cmath>
#include <cstdint>
/*
This program finds:
1. The first 10-digit prime number.
2. The last 10-digit prime number.
Strategy:
- Use uint64_t to safely handle 10-digit values.
- Implement a fast primality test using trial division up to sqrt(n).
This is efficient for single-number checks in the 10-digit range.
- Search upward from the smallest 10-digit number for the first prime.
- Search downward from the largest 10-digit number for the last prime.
- Check only odd numbers to reduce unnecessary work.
The code is structured for clarity:
- is_prime(...) performs primality testing.
- first_10_digit_prime() finds the smallest 10-digit prime.
- last_10_digit_prime() finds the largest 10-digit prime.
*/
// Determine whether a number is prime
bool is_prime(uint64_t n) {
if (n < 2) return false;
if (n % 2 == 0) return n == 2;
uint64_t limit = static_cast<uint64_t>(std::sqrt(n));
for (uint64_t d = 3; d <= limit; d += 2) {
if (n % d == 0) {
return false;
}
}
return true;
}
// Find the first 10-digit prime
uint64_t first_10_digit_prime() {
uint64_t n = 1'000'000'000ULL; // smallest 10-digit number
if (n % 2 == 0) {
++n; // move to next odd number
}
while (!is_prime(n)) {
n += 2; // check only odd numbers
}
return n;
}
// Find the last 10-digit prime
uint64_t last_10_digit_prime() {
uint64_t n = 9'999'999'999ULL; // largest 10-digit number
if (n % 2 == 0) {
--n; // move to previous odd number
}
while (!is_prime(n)) {
n -= 2; // check only odd numbers
}
return n;
}
int main() {
uint64_t first = first_10_digit_prime();
uint64_t last = last_10_digit_prime();
std::cout << "First 10-digit prime: " << first << "\n";
std::cout << "Last 10-digit prime: " << last << "\n";
}
/*
run:
First 10-digit prime: 1000000007
Last 10-digit prime: 9999999967
*/
