C - déterminer si un nombre est premier
Je suis en train d'essayer de trouver une méthode qui prend un entier et retourne un booléen pour dire si le nombre est premier ou pas et je ne connais pas trop C; est-ce que quelqu'un veut bien me donner quelques conseils?
En gros, je voudrais faire cela en C# comme ceci:
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
- C'est plus une question de mathématiques que d'une question de programmation, sûrement?
- Voici quelques pointeurs: int *ptr; int *ptr2; int *ptr3. Désolé ne pouvais pas l'aider. De quelle taille sont les numéros qui vous permettra de vérifier? Et aussi, vous avez envie d'une heuristique ou quelque chose qui fonctionne toujours?
- Venir avec vous de l'algorithme de la façon dont vous tester sans code) et puis on peut peut-être aider à l'exprimer en C.
- Pensez à un algorithme, essayez de la mettre en œuvre et si vous avez un problème concret avec elle, vous trouverez quelqu'un qui vous aide. Vous ne pouvez pas attendre pour d'autres sur l'intégralité de vos devoirs. De toute façon il y a un moyen facile de trouver une solution: il suffit d'utiliser la fonction de recherche--si vous la recherche pour "premier", vous trouverez beaucoup de bonnes approches.
- Quel est le point du " i != numéro lorsque vous avez "i < nombre' une condition de l'exécution de la boucle?
- Jetez un oeil à ce lien, il contient une explication de la façon dont les choses fonctionnent. cprogramming.language-tutorial.com/2012/01/...
- Notez également que la vérification
i < number
est exagéré. Par définition, si un certain nombrex = a * b
, soita
oub
est< int(sqrt(x))
et l'autre est plus grande. Si votre boucle ne devrait avoir besoin d'aller jusqu'àint(sqrt(x))
.
Vous devez vous connecter pour publier un commentaire.
OK, alors oubliez C. Supposons que je vous donne un numéro et vous demander pour déterminer s'il est premier. Comment voulez-vous faire? Écrivez les étapes clairement, puis vous soucier de les traduire en code.
Une fois que vous avez l'algorithme déterminé, il sera beaucoup plus facile pour vous de comprendre comment écrire un programme, et pour les autres de vous aider avec elle.
edit: Voici le code C# vous avez posté:
C'est très près de valide C est; il n'y a pas
bool
de type C, et pas detrue
oufalse
, si vous avez besoin de le modifier un peu (edit: Kristopher Johnson souligne à juste titre que le C99 ajouté le stdbool.h en-tête). Étant donné que certaines personnes n'ont pas accès à un C99 environnement (mais vous devez utiliser un seul!), faisons en sorte que cette modification mineure:C'est un bon programme C qui fait ce que vous voulez. Nous pouvons l'améliorer un peu, sans trop d'effort. Tout d'abord, notez que
i
est toujours inférieure ànumber
, de sorte que la vérification que lesi != number
réussit toujours; nous pouvons nous débarrasser de lui.Aussi, vous n'avez pas besoin d'essayer de diviseurs tout le chemin jusqu'à
number - 1
; vous pouvez arrêter la recherche lorsque vous atteignez sqrt(nombre). Depuissqrt
est une opération en virgule flottante et qui apporte tout un tas de subtilités, nous n'allons pas calculersqrt(number)
. Au lieu de cela, il nous suffit de vérifier quei*i <= number
:Une dernière chose, si; il y avait un petit bug dans votre algorithme original! Si
number
est négatif ou égal à zéro, ou un, cette fonction permet de prétendre que le nombre est premier. Il est probable que vous souhaitez gérer correctement, et vous pouvez fairenumber
est pas signé, puisque vous êtes plus susceptibles de soins sur les valeurs positives seulement:Ce n'est certainement pas le moyen le plus rapide pour vérifier si un nombre est premier, mais il fonctionne, et c'est assez simple. Nous avons à peine eu à modifier votre code à tout!
bool
,true
, etfalse
.i++
avec++i
. comme il diminuera également une étape de travail.i<number/i
pour éviter le débordement. Encore mieux, c'est de sauver le quotient et le reste par exemplefor(i=2, q=number/i, r=number%i; i<q; i++, q=number/i, r=number%i
).number/i
est strictement pire que de (pré-calculé)sqrt(number)
.number/i
effectue une division non nécessaire. Il fait aussi de la condition de la boucle dépend d'un long temps de latence de l'opération; sur une architecture en pipeline diviser, ce qui pourrait facilement provoquer des stands en raison des limites sur le nombre de problèmes non résolus de la branche des prédictions en vol à la fois.number%i
de sorte que vous obteneznumber/i
gratuitement. C'est tout aussi rapide quesqrt(number)
. Avez-vous lu mon conditional-tests-in-primality-by-trial-division?bool
true
etfalse
n'existe pas en C.static
fonctions existent dans C et les déclarations de variables à l'intérieur pour les boucles sont autorisés.i+=2
n'est pas droit. Vous pouvez essayer de saisie de 31 ou 33 pour le tester.IsPrime(0 or 1)
signale de manière incorrecte vrai. 2) un comportement Indéfini avecIsPrime(int number)
et grandnumber
, 3)IsPrime(unsigned number)
:i*i<=number
est un problème lorsque le numéro de près deUINT_MAX
commei*i
les débordements. Ligne de frontière boucle infinie lorsquenumber == UINT_MAX
.Je suis surpris que personne n'en a parlé.
Utiliser le Crible D'Eratosthène
Détails:
Le crible d'Eratosthène trouve un nombre premier et le stocke. Lorsqu'un nouveau numéro est vérifiée pour primeness tous les précédents sur les nombres premiers sont vérifiés sur le savoir, le premier de la liste.
Raisons:
O(n)
dans l'espace, et aussi longtemps que votre calcul est d'une seule valeur, c'est un énorme gaspillage d'espace pour aucun gain de performance.O(n log n)
ou plus si vous êtes en soutenant un grand nombre...)static const
bitmap de nombres qui sont le premier et l'utiliser, plutôt que de le remplir au moment de l'exécution..text
de la taille de segment.Stephen Canon répondu très bien!
Mais
C'est 3 fois plus rapide que les tests de tous les m jusqu'à √n.
0
quand (nombre == 1), que 1 n'est pas un nombre premier.ce programme est beaucoup plus efficace pour la vérification d'un numéro unique pour vérifier la primalité.
i=2
ài<=ceil(sqrt(n))
. Vous avez raté les 2 numéros dans votre test: tout d'Abord, fonte à(int)
faitsqrt(n)
tronc décimales. Deuxièmement, vous avez utiliséi<sq
, alors qu'elle devrait êtrei<=sq
. Maintenant, supposons qu'un nombre qui s'adapte à ce problème. Un nombre composén
qui aceil(sqrt(n))
comme le plus petit facteur. Votre intérieur de la boucle s'exécute pendant que j'aime: (5, 7), (11, 13), (17, 19), (23, 25), (29, 31), (35, 37), (41, 43), et ainsi de suite,n%i
etn%(i+2)
. Supposons que nous obtenonssqrt(1763)=41.98
. Étant1763=41*43
un nombre composé. Votre boucle sera exécuté uniquement jusqu'à ce que(35, 37)
et l'échec.ceil()
problème, j'ai réalisé que, bien que beaucoup de sites le recommande, c'est juste exagéré. Vous pouvez tronc et test justei<=sqrt(n)
et ça sera ok. Les cas de test sont de grands interpolation de nombres premiers. Exemple:86028221*86028223=7400854980481283
etsqrt(7400854980481283)~86028222
. Et les petits savons d'interpolation, les nombres premiers,2
et3
, donnesqrt(6)=2.449
que l'utilisation de plusieurs canaux laissera2
. (Mais de plus petite taille n'est pas un cas de test, juste une comparaison pour faire un point). Donc, oui, l'algorithme est correct maintenant. Pas besoin d'utiliserceil()
.Vérifier le module de chaque nombre entier de 2 à la racine du nombre que vous êtes arrivée.
Si le module est égal à zéro alors il n'est pas premier.
pseudo-code:
Après la lecture de cette question, j'ai été intrigué par le fait que certaines réponses que l'optimisation par l'exécution d'une boucle avec des multiples de 2*3=6.
J'ai donc créer une nouvelle fonction avec la même idée, mais avec des multiples de 2*3*5=30.
En exécutant les deux fonctions et la vérification de fois j'ai pu constater que cette fonction est vraiment plus rapide. Permet de voir 2 tests avec 2 différents nombres premiers:
Alors j'ai pensé, quelqu'un gain trop si généralisée? Je suis venu avec une fonction qui va faire un siège d'abord à nettoyer une liste donnée de primordial nombres premiers, et ensuite utiliser cette liste pour calculer le plus grand.
Je suppose que je n'ai pas d'optimiser le code, mais c'est juste. Maintenant, les tests. Parce que beaucoup de mémoire dynamique, je m'attendais à la liste 2 3 5 pour être un peu plus lent que les 2 3 5 codée en dur. Mais c'était ok comme vous pouvez le voir ci-dessous. Après cela, le temps obtenu plus en plus petits, culminant de la meilleure liste:
Avec 8,6 secondes. Donc si quelqu'un serait de créer un programme codé en dur qui rend l'utilisation de cette technique, je suggère d'utiliser la liste 2, 3 et 5, parce que le gain n'est pas si grand que ça. Mais aussi, si disposé à code, cette liste est ok. Problème est que vous ne peut pas indiquer tous les cas, sans boucle, ou votre code devrait être très grande (Il y aurait 1658879
ORs
, c'est-à||
dans les intérieurs respectifsif
). La liste suivante:temps, a commencé à obtenir plus, avec 13 secondes. Ici, l'ensemble du test:
PS. Je n'ai pas gratuite(r) intentionnellement, de donner cette tâche à l'OS, comme la mémoire sera libérée dès que le programme est sorti, pour gagner du temps. Mais il serait sage de le libérer si vous avez l'intention de garder l'exécution de votre code après le calcul.
BONUS
Temps:
101
-199
primals tous échoué ici parce que101 % (11+90)
.n%(i+86)
ou vérifiern > i+k
check235()
pour les nombres premiers 7, 11, 13, 17, 19, 23 et 29i+arr[k] >= n
if
avec des constantes peut être optimisé par le compilateur. J'ai édité pour ajouter une exception et de conserver la structure actuelle intact. Mais je suis d'accord, avec un tableau peut être mieux pour les yeux de l'homme.Je voudrais simplement ajouter que pas de même numéro de bar (2) peut être un nombre premier. Cela se traduit dans un autre état d'avant la boucle for. Pour que le bout de code devrait ressembler à ceci:
De manutention de 2 et même numéros sont gardés hors de la boucle principale, qui ne s'occupe que des nombres impairs divisé par un nombre impair. C'est parce qu'un nombre impair modulo un nombre pair donnera toujours un non-zéro réponse qui rend ces tests redondants. Ou, pour le dire d'une autre manière, un nombre impair peut être divisible par un autre nombre impair, mais jamais par un nombre pair (E*E=>E, E*O=>E, O*E=>E et O*O=>O).
Une division/module est vraiment coûteux sur l'architecture x86, bien que coûteux varie (voir http://gmplib.org/~tege/x86-timing.pdf). Multiplications d'autre part sont assez bon marché.
À l'aide de Crible d'Eratosthène, le calcul est assez rapide comparer à des "connus" à l'échelle de nombres premiers algorithme.
En utilisant des pseudo-code de wiki (https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes), je vais pouvoir avoir la solution sur C#.
IsPrimeNumber(1000000000) prend 21s 758ms.
NOTE: Valeur peut varier en fonction de spécifications matérielles.
Utilisation
for (i = 2; i <= number/i; i++)
pour limiter les itérations.number%i
,number/i
est efficace sur de nombreux compilateurs comme le calcul du quotient et le reste sont fait ensemble, ce qui n'entraînera aucun coût supplémentaire pour faire les deux ou juste 1.Une solution très simple: