fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. const int MAX = 1000000;
  5. bool isPrime[MAX + 1];
  6. long long primeList[80000];       // Tối đa ~78k số nguyên tố <= 1e6
  7. long long primePairs[80000];      // Chứa p[i] * p[i+1]
  8. int primeCount = 0;
  9. int pairCount = 0;
  10.  
  11. // Sàng nguyên tố đơn giản
  12. void sieve() {
  13.     for (int i = 0; i <= MAX; ++i)
  14.         isPrime[i] = true;
  15.  
  16.     isPrime[0] = isPrime[1] = false;
  17.  
  18.     for (int i = 2; i * i <= MAX; ++i) {
  19.         if (isPrime[i]) {
  20.             for (int j = i * i; j <= MAX; j += i)
  21.                 isPrime[j] = false;
  22.         }
  23.     }
  24.  
  25.     // Ghi lại các số nguyên tố
  26.     for (int i = 2; i <= MAX; ++i) {
  27.         if (isPrime[i]) {
  28.             primeList[primeCount++] = i;
  29.         }
  30.     }
  31.  
  32.     // Sinh các tích của 2 số nguyên tố liên tiếp
  33.     for (int i = 0; i + 1 < primeCount; ++i) {
  34.         long long product = primeList[i] * primeList[i + 1];
  35.         if (product > 1e12) break; // Giới hạn để tránh tràn
  36.         primePairs[pairCount++] = product;
  37.     }
  38. }
  39.  
  40. // Tìm phần tử lớn nhất trong primePairs[] mà ≤ n
  41. long long maxProductNotExceeding(long long n) {
  42.     int left = 0, right = pairCount - 1;
  43.     long long result = 0;
  44.  
  45.     while (left <= right) {
  46.         int mid = (left + right) / 2;
  47.         if (primePairs[mid] <= n) {
  48.             result = primePairs[mid];
  49.             left = mid + 1;
  50.         } else {
  51.             right = mid - 1;
  52.         }
  53.     }
  54.  
  55.     return result;
  56. }
  57.  
  58. int main() {
  59.     ios::sync_with_stdio(false);
  60.     cin.tie(nullptr);
  61.  
  62.     sieve(); // Chuẩn bị trước các cặp số nguyên tố
  63.  
  64.     int testCases;
  65.     cin >> testCases;
  66.  
  67.     while (testCases--) {
  68.         long long n;
  69.         cin >> n;
  70.         long long maxFit = maxProductNotExceeding(n);
  71.         cout << (n - maxFit) << '\n';
  72.     }
  73.  
  74.     return 0;
  75. }
  76. //code theo gpt =))
  77.  
Success #stdin #stdout 0.01s 5580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/x1ABV9
language:
C++ (gcc 8.3)
created:
2 days 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!