SOJ 1009. Mersenne Composite N

 1 #include <iostream>
 2 #include <vector>
 3 #include <ctime>
 4 using namespace std;
 5 
 6 const int maxn = 64;
 7 vector<int> primes;
 8 bool arr[maxn];
 9 
10 int n;
11 
12 void init() {
13     for (int i = 0; i < maxn; i++) {
14         arr[i] = true;
15     }
16 
17     for (int i = 2; i < maxn; i++) {
18         if (arr[i]) {
19             primes.push_back(i);
20             for (int j = 2; i * j < maxn; j++) {
21                 arr[i * j] = false;
22             }
23         }
24     }
25 }
26 
27 int main() {
28     cin >> n;
29     double start = clock();
30     init();
31     for (int i = 0; primes[i] <= n && primes[i] <= 59; i++) {
32         vector<long long> vt;
33 
34         long long m = ((long long)1 << primes[i]) - 1;
35 
36         for (long long i = 2; i * i <= m; i++) {
37             if (m % i == 0) {
38                 vt.push_back(i);
39                 m = m / i;
40             }
41         }
42 
43         if (m != 1) {
44             vt.push_back(m);
45         }
46 
47         if (vt.size() > 1) {
48             cout << vt[0];
49             for (int i = 1; i < vt.size(); i++) {
50                 cout << " * " << vt[i];
51             }
52             cout << " = " << ((long long)1 << primes[i]) - 1 << " = ( 2 ^ " << primes[i] << " ) - 1" << endl;
53         }
54 
55     }
56     double end = clock();
57     cout << (end - start) / CLOCKS_PER_SEC << endl;
58 
59     return 0;
60 }