Given the task: In the interval [a,b] output all numbers such that the sum of their divisors, including one, and not including the number itself will be equal to the number itself. Or -1 , if there are no such numbers in the interval.

It is necessary to optimize the search algorithm so that the program does not hang when working with large numbers. Simply so that after 80 000 does not report Time limit exceeded Killed . I have not used many types of variables and algorithms yet, therefore information on this topic is also important.

 #include <stdio.h> int main(){ int a, b; scanf("%d %d", &a, &b); int counter = 0; for(int i = a; i <= b; i++) { int sum = 0; for(int j = 1; j < i; j++) { if(i % j == 0) { sum += j; } } if(sum == i) { printf("%d ", i); counter++; } } if(counter == 0) { printf("-1"); } return 0; }
  • It is easier to take a ready-made plate (it is small) than to count ... The second option is to count the numbers of Mersenne. - Harry
  • @Harry, okay? By the way, what does it have to do with Mersen? They are simple like? - Qwertiy ♦
  • Precisely :) For ... Kolupaev decomposition count. And about the Mersenne numbers ... So in the meantime, so far all the perfect numbers found from the Mersenne numbers are obtained. - Harry
  • Let's continue the discussion in the chat . - Qwertiy ♦ pm

2 answers 2

So, if you really want to count it ... taking advantage of the fact that all perfect numbers known to date are even, and Euler proved their connection with Mersenne primes - so we select simple Mersenne numbers that provide perfect numbers in the right range:

Disclaimer: code as is, piled on the knee, just to show how it should work. With all the subtleties of sizes and other, please handle yourself and not touch me :)

 #include <stdlib.h> #include <stdio.h> #include <string.h> int isOddPrime(unsigned int u) { for(unsigned int i = 3; i*i <= u; i+=2) if (u%i == 0) return 0; return 1; } unsigned int Perfect(unsigned int p) { unsigned int Mersenne = (1u << p) - 1; if (!isOddPrime(Mersenne)) return 0; return Mersenne*(1u << (p-1)); } int main() { unsigned int a, b; scanf("%u %u",&a,&b); for(unsigned int p = 2;;++p) { unsigned long long s = (1ull << (2*p-1)) - (1ull << (p-1)); if (s > b) break; if (s < a) continue; unsigned int res = Perfect(p); if (res) printf("%lu\n",res); } }

Conclusion to the desired form (well, there, -1 if there are no numbers, etc.) give yourself ...

PS In general, the most correct program on this topic -

 #include <stdlib.h> #include <stdio.h> unsigned long long perfs[] = { 6,28,496,8128,33550336,8589869056, 137438691328,2305843008139952128 }; int main() { unsigned long long a, b; scanf("%llu %llu",&a,&b); int was = 0; for(int i = 0; i < 8; ++i) { if (perfs[i] >= a && perfs[i] <= b) { was = 1; printf("%llu\n",perfs[i]); } } if (!was) puts("-1"); }

:)

PPS All the necessary information was very easy to get by walking, for example, to Wikipedia .

  • 1. unsigned long -> unsigned long long , but not all linux. 2. (2 << p) - 1 - should be 2ULL . 3. In the check for simplicity, even numbers should have return u==2; - Qwertiy ♦
  • @Qwertiy 1. An unsigned long should suffice - an unsigned long is encountered once only to avoid overflow for large numbers. 2. I agree corrected. 3. Damn, it is not needed at all, my puncture is only odd in the same place ... It just does not work :) - Harry
  • 1. unsigned long is 32 bits on Windows, but 64 on Linux. Sense to use such a dubious type? 3. Well, just so that the verification function is universal. - Qwertiy ♦
  • @Qwertiy Change to unsigned int . I was throwing "on my knee", I was in a hurry, just to show an idea ... - Harry
  • @Harry 2ul is that with such a record, I have not yet come across such a record - Astrodynamic

Use an algorithm based on the same approach as the sieve of Eratosthenes. Make an array with the sum of dividers different from the number itself, and then count the number of suitable numbers.

 var a = Array(1000000+1).fill(0) for (var q=1; q<a.length; ++q) for (var w=q+q; w<a.length; w+=q) a[w] += q var l=1, r=1000000, res=0 for (var x=l; x<=r; ++x) if (a[x] === x) console.log(x)