fork download
copy 
  1. #include <iostream>
  2. #include <cassert>
  3.  
  4. const int maxprime = 65536;
  5.  
  6. int primes[maxprime];
  7. int nprimes;
  8.  
  9. void findPrimes() {
  10.     std::cout << "Searching prime numbers ..." << std::endl;
  11.     bool *sieve = new bool[maxprime+1];
  12.     int i;
  13.     for (i=0;i<maxprime;i++)
  14.         sieve[i] = 0;
  15.     i = 2;
  16.     nprimes = 0;
  17.     while (1) {
  18.         while (i<maxprime && sieve[i])
  19.             i++;
  20.         if (i>=maxprime)
  21.             break;
  22.         primes[nprimes++] = i;
  23.         for (int j=i*2; j<maxprime; j+=i)
  24.             sieve[j] = 1;
  25.         i++;
  26.     }
  27.     std::cout << nprimes << " primes found" << std::endl;
  28.     delete sieve;
  29. }
  30.  
  31. int sumDiv(int a) {
  32.     int i, r=1, b=a;
  33.     int *pr = primes;
  34.     while (b > 1) {
  35.         int p = *pr++, s = 1;
  36.         if (p*p > b)
  37.             return r * (b+1) - a;
  38.         while (b % p == 0) {
  39.             b /= p;
  40.             s = s*p + 1;
  41.         }
  42.         r *= s;
  43.     }
  44.     return r;
  45. }
  46.  
  47. int main() {
  48.     findPrimes();
  49.     int cnt = 0;
  50.     for (int a=1; ; a++) {
  51.         int b = sumDiv(a);
  52.         if (a < b && sumDiv(b) == a) {
  53.             cnt++;
  54.             std::cout << cnt << " (" << a << ", " << b << ")" << std::endl;
  55.             if (cnt == 30)
  56.                 break;
  57.         }
  58.     }
  59.     return 0;
  60. }
Success #stdin #stdout 0.59s 3068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Searching prime numbers ...
6542 primes found
1 (220, 284)
2 (2620, 2924)
3 (5020, 5564)
4 (6232, 6368)
5 (10744, 10856)
6 (12285, 14595)
7 (17296, 18416)
8 (63020, 76084)
9 (66928, 66992)
10 (67095, 71145)
11 (69615, 87633)
12 (79750, 88730)
13 (100485, 124155)
14 (122265, 139815)
15 (122368, 123152)
16 (141664, 153176)
17 (142310, 168730)
18 (171856, 176336)
19 (176272, 180848)
20 (185368, 203432)
21 (196724, 202444)
22 (280540, 365084)
23 (308620, 389924)
24 (319550, 430402)
25 (356408, 399592)
26 (437456, 455344)
27 (469028, 486178)
28 (503056, 514736)
29 (522405, 525915)
30 (600392, 669688)
https://ideone.com/kyLGMK
language:
C++ (gcc 8.3)
created:
13 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!