Zählen Sie von 1 bis n, wie viele Ganzzahlen es gibt, wenn die Summe der Divisors eine Primzahl ist? ⇐ C++

[Guest]

Lassen Sie es Ganzzahl n. P> Beispiel: < /p>
Eingabe: 10 < /p>
Ausgabe: 3 < /p>
Erläuterung: Es gibt 3 Zahlen mit Die Summe der Divisors ist eine Prime: 2,4,9. 4: 1,2,4: sum = 1+2+4 = 7
9: 1,3,9: sum = 1+3+9 = 13 < Br /> Ich habe dieses Problem von einem vietnamesischen Wettbewerb genommen. Zuerst habe ich versucht, es mit einer Funktion zu lösen, um Divisoren und das Sieb von Eratosthenen zu berechnen, kann aber nur in O (n log n) ausgeführt werden, was für n = 10^9 . Hat jemand eine Idee, was ist die beste Lösung, um zu zählen, wie viele Zahlen es gibt, wenn die Summe der Divisors eine Primzahl ist? Von Papier gibt es leider keine Quelle davon. Wenn es so wäre, hätte ich es getan, ohne zu fragen.