Comment trouver un nombre en une somme de nombres premiers?
Permet de voir que nous voulons trouver tous les nombres entre 1 et 1 000 qui sont représenté comme une somme de deux nombres premiers. e.g 8 = 3+5, 24 = 13+11
Maintenant, cela peut être fait en O(n^2) en parcourant la liste des nombres premiers entre 1 et 1 000.
Est-il de toute façon de faire la même chose en moins de O(n^2).Est-il une méthode pour faire cela en temps linéaire ?
"La conjecture de Goldbach est l'un de la plus ancienne et la mieux connue des problèmes non résolus dans la théorie des nombres et dans toutes les mathématiques. Il dispose que: "Tout nombre entier pair supérieur à 2 peut être exprimé comme la somme de deux nombres premiers." : en.wikipedia.org/wiki/Goldbach's_conjecture
Si seulement des nombres premiers distincts sont-ils autorisés ?.
Si seulement des nombres premiers distincts sont-ils autorisés ?.
OriginalL'auteur user1822249 | 2013-02-06
Vous devez vous connecter pour publier un commentaire.
Faire un tableau
p
de 1000 booléens. Ensemblep[i]
àtrue
sii
est premier, etfalse
autrement.Puis le
O(N^2)
algorithme devient facile: allez par le biais de numéros dek
1 à 1000 dans la boucle externe, puis passez par tous les nombres premiersx
plus dek
dans une boucle interne, et de vérifier s'il existe un nombre premier tel quep[k-x]
esttrue
:Je doute que la vérification peut être effectuée en temps constant pour un temps total d'exécution de
O(N)
pour les 1000 numéros, parce que la vérification assistée par ordinateur actuellement produit à des vitesses lentes.OriginalL'auteur dasblinkenlight
Pour tous les nombres pairs, nous savons maintenant, ils ont peut être représenté comme la somme de 2 nombres premiers(voir La conjecture de Goldbach)
Pour tous les nombres impairs, si elle peut être représentée comme la somme de 2 nombres premiers, l'un d'eux doit être de 2, et l'autre doit être un nombre premier impair.
De sorte que le nombre total doit être (1000/2 - 1) + (nombre premier comte de 3 à 997),
dans lequel,
(1000/2 - 1) est le nombre total de séries de 4, 6, 8, 10...
(le premier nombre de 3 (997) est le nombre total de séries 5(2+3), 7(2+5), 9(2+7), 13(2+11) ...
OriginalL'auteur zTrix
1 ! 1 est une bonne formule pour cette. le premier n', 1000 + 1 divisé par 5x + 38. ce n'est conformément à l'ATF Théorème. essayez cela et vous obtiendrez la réponse.
OriginalL'auteur user7864921
OriginalL'auteur Saurabh Pawar