fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Miller-Rabin Primality Test
  5. bool millerRabin(long long n, long long a) {
  6.     if (n <= 1) return false;
  7.     if (n == 2) return true;
  8.     if (n % 2 == 0) return false;
  9.  
  10.     // Write n-1 as d * 2^r
  11.     long long d = n - 1;
  12.     int r = 0;
  13.     while (d % 2 == 0) {
  14.         d /= 2;
  15.         r++;
  16.     }
  17.  
  18.     // Modular exponentiation: a^d mod n
  19.     auto modPow = [](long long base, long long exp, long long mod) {
  20.         long long result = 1;
  21.         base %= mod;
  22.         while (exp > 0) {
  23.             if (exp & 1) result = (__int128)result * base % mod;
  24.             base = (__int128)base * base % mod;
  25.             exp >>= 1;
  26.         }
  27.         return result;
  28.     };
  29.  
  30.     long long x = modPow(a, d, n);
  31.     if (x == 1 || x == n - 1) return true;
  32.  
  33.     for (int i = 0; i < r - 1; i++) {
  34.         x = (__int128)x * x % n;
  35.         if (x == n - 1) return true;
  36.     }
  37.     return false;
  38. }
  39.  
  40. bool isPrime(long long n) {
  41.     if (n <= 1) return false;
  42.     if (n <= 3) return true;
  43.     if (n % 2 == 0 || n % 3 == 0) return false;
  44.  
  45.     // Check small primes first
  46.     vector<int> smallPrimes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  47.     for (int p : smallPrimes) {
  48.         if (n == p) return true;
  49.         if (n % p == 0) return false;
  50.     }
  51.  
  52.     // Miller-Rabin with deterministic witnesses for n < 3,317,044,064,679,887,385,961,981
  53.     vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
  54.     for (long long a : witnesses) {
  55.         if (a >= n) continue;
  56.         if (!millerRabin(n, a)) return false;
  57.     }
  58.     return true;
  59. }
  60.  
  61. // Method 1: Simple backward iteration (Recommended for most cases)
  62. long long largestPrimeSimple(long long n) {
  63.     if (n <= 1) return -1;
  64.     if (n == 2) return 2;
  65.  
  66.     // Start from n (or n-1 if n is even)
  67.     if (n % 2 == 0) n--;
  68.  
  69.     for (long long i = n; i >= 2; i -= 2) {
  70.         if (isPrime(i)) return i;
  71.     }
  72.     return 2; // Should never reach here
  73. }
  74.  
  75. // Method 2: Optimized with gap estimation
  76. long long largestPrimeOptimized(long long n) {
  77.     if (n <= 1) return -1;
  78.     if (n == 2) return 2;
  79.  
  80.     // For small numbers, use simple method
  81.     if (n <= 1000) return largestPrimeSimple(n);
  82.  
  83.     // Estimate maximum gap (Bertrand's postulate: gap < n for large n)
  84.     // In practice, gaps are much smaller: O(log n)
  85.     long long maxGap = min(n, (long long)(log(n) * log(n) * 10));
  86.  
  87.     long long start = (n % 2 == 0) ? n - 1 : n;
  88.  
  89.     for (long long i = start; i >= max(2LL, n - maxGap); i -= 2) {
  90.         if (isPrime(i)) return i;
  91.     }
  92.  
  93.     // Fallback to simple method if not found in estimated range
  94.     return largestPrimeSimple(n - maxGap);
  95. }
  96.  
  97. // Method 3: Using precomputed small primes for trial division
  98. vector<int> smallPrimes;
  99.  
  100. void generateSmallPrimes() {
  101.     const int LIMIT = 100000;
  102.     vector<bool> sieve(LIMIT + 1, true);
  103.     sieve[0] = sieve[1] = false;
  104.  
  105.     for (int i = 2; i * i <= LIMIT; i++) {
  106.         if (sieve[i]) {
  107.             for (int j = i * i; j <= LIMIT; j += i) {
  108.                 sieve[j] = false;
  109.             }
  110.         }
  111.     }
  112.  
  113.     for (int i = 2; i <= LIMIT; i++) {
  114.         if (sieve[i]) smallPrimes.push_back(i);
  115.     }
  116. }
  117.  
  118. bool isPrimeFast(long long n) {
  119.     if (n <= 1) return false;
  120.     if (n <= smallPrimes.back()) {
  121.         return binary_search(smallPrimes.begin(), smallPrimes.end(), n);
  122.     }
  123.  
  124.     // Trial division with small primes
  125.     for (int p : smallPrimes) {
  126.         if ((long long)p * p > n) break;
  127.         if (n % p == 0) return false;
  128.     }
  129.  
  130.     // Miller-Rabin for larger numbers
  131.     return isPrime(n);
  132. }
  133.  
  134. long long largestPrimeFast(long long n) {
  135.     if (smallPrimes.empty()) generateSmallPrimes();
  136.  
  137.     if (n <= 1) return -1;
  138.     if (n == 2) return 2;
  139.  
  140.     if (n % 2 == 0) n--;
  141.  
  142.     for (long long i = n; i >= 2; i -= 2) {
  143.         if (isPrimeFast(i)) return i;
  144.     }
  145.     return 2;
  146. }
  147.  
  148. int main() {
  149.     ios_base::sync_with_stdio(false);
  150.     cin.tie(NULL);
  151.  
  152.     // Test cases
  153.     vector<long long> testCases = {
  154.         10, 100, 1000, 10000, 100000, 1000000,
  155.         436273036, 436273290, 436273036
  156.     };
  157.  
  158.     cout << "Testing largest prime finder:\n";
  159.     cout << "N\t\tLargest Prime <= N\n";
  160.     cout << "--------------------------------\n";
  161.  
  162.     for (long long n : testCases) {
  163.         long long result = largestPrimeSimple(n);
  164.         cout << n << "\t\t" << result << "\n";
  165.     }
  166.  
  167.     // Interactive mode
  168.     cout << "\nEnter numbers to find largest prime (0 to exit):\n";
  169.     long long n;
  170.     while (cin >> n && n != 0) {
  171.         if (n < 2 || n > 1000000000) {
  172.             cout << "Invalid input. Range: 2 <= n <= 10^9\n";
  173.             continue;
  174.         }
  175.  
  176.         auto start = chrono::high_resolution_clock::now();
  177.         long long result = largestPrimeSimple(n);
  178.         auto end = chrono::high_resolution_clock::now();
  179.  
  180.         auto duration = chrono::duration_cast<chrono::microseconds>(end - start);
  181.  
  182.         cout << "Largest prime <= " << n << " is: " << result;
  183.         cout << " (Time: " << duration.count() << " microseconds)\n";
  184.     }
  185.  
  186.     return 0;
  187. }
  188.  
  189. /*
  190. Time Complexity: 
  191. - Average case: O(log n) iterations × O(log³ n) per primality test = O(log⁴ n)
  192. - Worst case: O(√n) for very unlucky gaps
  193.  
  194. Space Complexity: O(1) for basic version, O(√n) for optimized with small primes
  195.  
  196. For n = 10^9:
  197. - Expected iterations: ~23 (average prime gap)
  198. - Time per test: ~1ms
  199. - Total time: Usually < 50ms
  200. */
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Testing largest prime finder:
N		Largest Prime <= N
--------------------------------
10		7
100		97
1000		997
10000		9973
100000		99991
1000000		999983
436273036		436273009
436273290		436273009
436273036		436273009

Enter numbers to find largest prime (0 to exit):
https://ideone.com/7d6IMQ
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!