fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. #include <algorithm> // __gcd()
  5. #include <cstring> // memset()
  6. #include <cassert> // assert()
  7.  
  8. using namespace std;
  9.  
  10. #define int long long
  11. typedef long double dbl;
  12.  
  13. const int N=2e6+10;
  14.  
  15. int np, prime[N];
  16. bool isp[N];
  17. void sieve(int N) {
  18.     memset(isp, true, sizeof isp);
  19.     isp[0] = isp[1] = false;
  20.     for(int i=2; i<N; i++) if(isp[i]) {
  21.         prime[++np]=i;
  22.         for(int j=2*i; j<N; j+=i) {
  23.             isp[j]=false;
  24.         }
  25.     }
  26. }
  27.  
  28. inline int mul(int a, int b, int m) {
  29. 	a%=m; if(a<0) a+=m;
  30. 	b%=m; if(b<0) b+=m;
  31. 	int q = ((dbl)a * (dbl)b) / (dbl)m;
  32. 	int r = a*b - q*m;
  33. 	return (r<0 ? r+m:r);
  34. }
  35. inline int pwr(int a, int n, int m) {
  36.     int ans(1);
  37.     while(n) {
  38.         if(n & 1) ans = mul(ans, a, m);
  39.         if(n >>= 1) a = mul(a, a, m);
  40.     }
  41.     return ans%m;
  42. }
  43. int myrand(int n) {
  44. 	return rand()%n*rand()%n*rand()%n;
  45. }
  46. bool ispmiller(int p) { // O(30*logp)
  47. 	if(p<2) return false;
  48. 	if(p==2) return true;
  49. 	if(p%2==0) return false;
  50. 	int s=p-1; s>>=__builtin_ctzll(s);
  51. 	for(int i=0; i<60; i++) {
  52. 		int val=pwr(myrand(p-1)+1,s,p), temp=s;
  53. 		while(temp!=p-1 and 1<val and val<p-1) {
  54. 			val=mul(val,val,p);
  55. 			temp<<=1;
  56. 		}
  57. 		if(val!=p-1 and temp%2==0) return false;
  58. 	}
  59. 	return true;
  60. }
  61. inline int pollardrho(int n) { // O(n^0.25)
  62. 	if(n==1) return 1;
  63. 	if(n%2==0) return 2;
  64. 	int c=myrand(n-1)+1, x=myrand(n-2)+2, y=x;
  65. 	int d=1; while(d==1) {
  66. 		x=mul(x,x,n)+c; if(x>=n) x-=n;
  67. 		y=mul(y,y,n)+c; if(y>=n) y-=n;
  68. 		y=mul(y,y,n)+c; if(y>=n) y-=n;
  69. 		d=__gcd(abs(x-y),n);
  70. 		if(d==n) return (ispmiller(n) ? n:pollardrho(n));
  71. 	}
  72. 	return d;
  73. }
  74.  
  75. #undef int
  76. int main() {
  77. #define int long long
  78. 	int t;
  79. 	while(t--){
  80.     int n; cin >> n;
  81.     if(ispmiller(n)) {
  82.     	cout << n << '\n'; // input n is prime, output as it is
  83.     	return 0;
  84.     }
  85.  
  86.     vector<int> factors; // holds the prime factorisation of input n
  87.  
  88.     sieve(1e6);
  89.     for(int i=1; i<np and prime[i]*prime[i]<=n; i++) {
  90.     	if(n%prime[i]==0) { // n is divisible by prime[i] (<= 1e6)
  91.     		while(n%prime[i]==0) {
  92.     			n /= prime[i];
  93.     			factors.push_back(prime[i]);
  94.     		}
  95.     	}
  96.     }
  97.  
  98.     if(ispmiller(n)) {
  99.     	factors.push_back(n);
  100.     }
  101.     else if(n>1) { // n still has some prime factors > 1e6
  102.     	int x = pollardrho(n);
  103.     	assert(x > 1e6);
  104.     	factors.push_back(x);
  105.     	factors.push_back(n/x);
  106.     }
  107.  
  108.     // Print the factorisation
  109.     for(int i=0; i<(int)factors.size()-1; i++) cout << factors[i] << '*';
  110. 	cout << (factors.empty() ? 1 : factors.back()) << '\n';
  111. 	}
  112.     return 0;
  113. }
Success #stdin #stdout 0s 4892KB
comments (?)
stdin
copy 
2 
14 
11
stdout
copy 
Standard output is empty
https://ideone.com/TcwMPL
language:
C++14 (gcc 8.3)
created:
4 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!