From 1 to n, count how many integers there are with the sum of divisors being a prime number?

Question

Let there be integer n.

Count how many numbers there are from 1 to n that has the sum of divisors being a prime number.

Example:

Input: 10

Output: 3

Explanation: There are 3 numbers with the sum of divisors being a prime: 2,4,9.

2: 1,2: Sum = 1+2 = 3.

4: 1,2,4: Sum = 1+2+4 = 7

9: 1,3,9: Sum = 1+3+9 = 13

I took this problem from a Vietnamese contest. At first I tried to solve it using a function to calculate divisors and the Sieve of Eratosthenes, but it can only run in O(n log n), which isn't plausible for n = 10^9. Does anyone have any idea what's the best solution to count how many numbers there are with the sum of divisors being a prime number?

Edit: It's from a piece of paper, there's no source of this unfortunately. If there were, I would've done so without asking.

Answer 1

When you do not know whether the sum is prime or not, then you need to actually compute it.

However, there are general ideas that you can apply, such as:

• if the sum has a pair amount of odd divisor types, then it's divisible with two, hence you do not need to check whether it's prime, you'll instantly know whether it's prime (equals 2) or not
• if the sum's last digit is 0 or 5, then it's divisible with 5
• if the sum of the sum's digit is 0, 3, 6 or 9, then it's divisible by 3

These ideas can be applied to drastically reduce the number of sums whose prime-ness you are to check. If all these quickening rules fail to determine for a sum whether it's prime, then you will need to do the costly prime calculation, but it would be a much rarer necessity, than without these pre-filters.