fork(7) download
copy 
  1. #include <stdio.h>
  2.  
  3.  
  4.  
  5. int main()
  6. {
  7. 	int i,j;
  8. 	const int N = 20000000;
  9. 	const int CNT_PRIMES = N; // upper bound on number of primes within range from 1 to N
  10.  
  11. 	int smallest_divisor[N];
  12. 	int sigma[N];
  13. 	int sum_proper[N];
  14. 	int primes[CNT_PRIMES];
  15. 	int curcnt = 0;
  16. 	for (i = 2; i < N; ++i)
  17.         smallest_divisor[i] = i;
  18.     for ( i = 2; i < N; ++i)
  19.     {
  20.         if (smallest_divisor[i] == i)
  21.             primes[curcnt++] = i;
  22.         for (j = 0; j < curcnt && primes[j] <= smallest_divisor[i] && primes[j] * i < N; ++j)
  23.             smallest_divisor[primes[j] * i] = primes[j];
  24.     }
  25.     sigma[1] = 1;
  26.     for (i = 2; i < N; ++i)
  27.     {
  28.         int cur = i;
  29.         int p = smallest_divisor[i];
  30.         int k = 0;
  31.         while (cur % p == 0)
  32.             cur /= p, ++k;
  33.         int pk = i / cur;
  34.         sigma[i] = (pk * p - 1) / (p - 1); // sigma(p^k) = 1 + p + ... + p^k = (p^(k+1) - 1) / (p - 1)
  35.         sigma[i] *= sigma[cur];
  36.         sum_proper[i] = sigma[i] - i;
  37.     }
  38.     for (i = 2; i < N; ++i)
  39.     {
  40.         int j = sum_proper[i];
  41.         if (j < N && j > i && sum_proper[j] == i)
  42.             printf("%d\t\t%d\n", i, j);
  43.     }
  44.     return 0;
  45. }
Success #stdin #stdout 0.76s 241056KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
220		284
1184		1210
2620		2924
5020		5564
6232		6368
10744		10856
12285		14595
17296		18416
63020		76084
66928		66992
67095		71145
69615		87633
79750		88730
100485		124155
122265		139815
122368		123152
141664		153176
142310		168730
171856		176336
176272		180848
185368		203432
196724		202444
280540		365084
308620		389924
319550		430402
356408		399592
437456		455344
469028		486178
503056		514736
522405		525915
600392		669688
609928		686072
624184		691256
635624		712216
643336		652664
667964		783556
726104		796696
802725		863835
879712		901424
898216		980984
947835		1125765
998104		1043096
1077890		1099390
1154450		1189150
1156870		1292570
1175265		1438983
1185376		1286744
1280565		1340235
1328470		1483850
1358595		1486845
1392368		1464592
1466150		1747930
1468324		1749212
1511930		1598470
1669910		2062570
1798875		1870245
2082464		2090656
2236570		2429030
2652728		2941672
2723792		2874064
2728726		3077354
2739704		2928136
2802416		2947216
2803580		3716164
3276856		3721544
3606850		3892670
3786904		4300136
3805264		4006736
4238984		4314616
4259750		4445050
4482765		5120595
4532710		6135962
4604776		5162744
5123090		5504110
5147032		5843048
5232010		5799542
5357625		5684679
5385310		5812130
5459176		5495264
5726072		6369928
5730615		6088905
5864660		7489324
6329416		6371384
6377175		6680025
6993610		7158710
7275532		7471508
7288930		8221598
7489112		7674088
7577350		8493050
7677248		7684672
7850512		8052488
8262136		8369864
8619765		9627915
8666860		10638356
8754130		10893230
8826070		10043690
9071685		9498555
9199496		9592504
9206925		10791795
9339704		9892936
9478910		11049730
9491625		10950615
9773505		11791935
10254970		10273670
10533296		10949704
10572550		10854650
10596368		11199112
10634085		14084763
10992735		12070305
11173460		13212076
11252648		12101272
11498355		12024045
11545616		12247504
11905504		13337336
12397552		13136528
12707704		14236136
13671735		15877065
13813150		14310050
13921528		13985672
14311688		14718712
14426230		18087818
14443730		15882670
14654150		16817050
15002464		15334304
15363832		16517768
15938055		17308665
16137628		16150628
16871582		19325698
17041010		19150222
17257695		17578785
17754165		19985355
17844255		19895265
17908064		18017056
18056312		18166888
18655744		19154336
https://ideone.com/JJSivZ
language:
C (gcc 8.3)
created:
6 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!