Le calcul de phi(k) pour 1<k<N

Donné un grand N, j'ai besoin de parcourir tous les phi(k) telle que 1 < k < N :

  • temps-la complexité doit être O(N logN)
  • de la mémoire-la complexité doit être sous O(N) (puisque les valeurs de N sera d'environ 1012)

Est-il possible? Si oui, comment?

  • Un Projet d'Euler?
  • Voir "Combien de nombres inférieurs à N sont premiers entre eux N?": stackoverflow.com/questions/1019040/... à propos de la même question: comment calculer phi(k) rapidement.
  • Ce n'est pas un Projet d'Euler, mais elle a été engendrée par l'un de leurs problèmes que j'ai maintenant résolu.
  • Qu'est-ce que "rapidement"?
  • ShreevatsaR: Cette question a été sur le calcul de Phi(k) dans l'isolement. Cette question est sur le calcul de tous les Phi(k) dans la séquence jusqu'à un certain N. C'est lié, mais encore significativement différente de la question.
  • Au hasard: c'est l'ordre d'itération important?
  • Jamais l'esprit; je n'ai pu avoir de la mémoire de la complexité en bas à O(x/ln(x)) ou alors...
  • L'ordre n'est pas important; "rapidement" est un membre de O(n log n).

InformationsquelleAutor | 2009-06-21