fork(4) download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <cctype>
  6. using namespace std;
  7. long long mulmod(long long a, long long b, long long c)
  8. {
  9. long long x = 0, y = a%c;
  10. while(b>0)
  11. {
  12. if(b&1) x = (x+y)%c;
  13. y = (y<<1)%c;
  14. b = b>>1;
  15. }
  16. return x;
  17. }
  18. long long modulo(long long a, long long b, long long c)
  19. {
  20. long long x = 1, y = a%c;
  21. while(b>0)
  22. {
  23. if(b&1) x = mulmod(x,y,c);
  24. y = mulmod(y,y,c);
  25. b = b>>1;
  26. }
  27. return x;
  28. }
  29. bool miller(long long p, int iter)
  30. {
  31. if(p<2) return false;
  32. if(p==2) return true;
  33. if(!(p&1)) return false;
  34. long long s = p-1, a, temp, mod;
  35. while(!(s&1)) s = s>>1;
  36. for(int i=0; i<iter; i++)
  37. {
  38. a = rand()%(p-1)+1;
  39. temp = s;
  40. mod = modulo(a, temp, p);
  41. while(temp!=p-1 && mod!=1 && mod!=p-1)
  42. {
  43. mod = mulmod(mod, mod, p);
  44. temp = temp<<1;
  45. }
  46. if(mod!=p-1 && !(temp&1)) return false;
  47. }
  48. return true;
  49. }
  50. int main()
  51. {
  52. long long t,n,i;
  53.  
  54. scanf("%lld", &t);
  55.  
  56. while ( t-- ) {
  57. scanf("%lld", &n);
  58. for ( i = n;; i-- ) {
  59. if ( miller(i,2) ) {
  60. printf("%lld\n", i);
  61. break;
  62. }
  63. }
  64. }
  65.  
  66. return 0;
  67. }
  68.  
Success #stdin #stdout 0s 2732KB
comments (?)
stdin
copy 
2
100000000000000000
1000000000000000000
stdout
copy 
99999999999999997
999999999999999989
https://ideone.com/mApYtQ
language:
C++ 4.3.2 (gcc-4.3.2)
created:
12 years 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!