J'ai récemment faisait partie d'un petit concours de programmation Java à mon école. Mon partenaire et moi venons de terminer notre première classe PURE OOP et que la plupart des questions étaient sorties de notre ligue, nous sommes donc installés sur celui-ci (et je suis paraphrasant quelque peu): "Étant donné une entrée entier N retourner le prochain int qui est prime et Son inverse est également prime, par exemple, si N = 18 Votre programme devrait imprimer 31 "car 31 et 13 sont à la fois primordiaux. Votre fichier .Class aurait alors un cas de test de tous les numéros possibles de 1 à 2 000 000 000 qui lui ont été transmis et il devait renvoyer la bonne réponse dans les 10 secondes pour être considérée comme valide.
Nous avons trouvé une solution mais avec des cas de test plus vastes, il faudra plus de 10 secondes. Je suis assez certain qu'il y a un moyen de déplacer la gamme de boucles de N, .. 2 000 000 000 000 en tant que capot probable de devoir boucle que loin lorsque n est un nombre bas est petit, mais de toute façon nous avons cassé la boucle lorsqu'un nombre est préféré dans les deux conditions est trouvé. Au début, nous étions en boucle de 2, .. n Peu importe la taille de la taille, je me suis alors souvenu de la règle de la flèche de la racine carrée de n. Des suggestions sur la manière de rendre mon programme plus efficace? Je n'ai eu aucune classe traitant de l'analyse de la complexité des algorithmes. Voici notre tentative. P>
public class P3
{
public static void main(String[] args){
long loop = 2000000000;
long n = Integer.parseInt(args[0]);
for(long i = n; i<loop; i++)
{
String s = i +"";
String r = "";
for(int j = s.length()-1; j>=0; j--)
r = r + s.charAt(j);
if(prime(i) && prime(Long.parseLong(r)))
{
System.out.println(i);
break;
}
}
System.out.println("#");
}
public static boolean prime(long p){
for(int i = 2; i<(int)Math.sqrt(p); i++)
{
if(p%i==0)
return false;
}
return true;
}
}
11 Réponses :
On dirait que vous êtes incrémenté par 1, mais vous devriez être incrémenté par 2. Aucun numéro même n'est prime mais 2.
C'est une faute de frappe réellement. J'ai réécrit cela de la mémoire mais merci pour cela.
Tout d'abord, vous devez précomputer tous les nombres premiers jusqu'à 2 000 000 000 en utilisant quelque chose comme le Sieve of Eratosthenes . Vous pouvez stocker si chaque numéro est prime dans un tableau de bits.
Ceci est assez rapide, puis en vérifiant chaque numéro individuel pour la primalité est une recherche simple.
Si vous ne pouvez pas faire cela parce que vous devez exécuter une nouvelle instance de votre programme pour chaque cas de test, utilisez un algorithme de test de primalité rapide comme
Je me demande si le précompement sur les réponses serait considéré comme tricherie - après tout, s'ils connaissent les nombres premiers de 1 à 2 milliards d'avances à l'avance, trouver l'ensemble dans ce groupe qui est également "inverse Prime" pourrait également être effectué. Ensuite, c'est juste une question triviale de «quel nombre dans mon ensemble précalculé est l'entrée la plus proche de?
@MMR: L'utilisation d'un meilleur algorithme ne triche pas - il s'agit simplement d'être intelligent et d'utiliser toutes les informations données pour optimiser votre programme.
@ David-- Je ne suis pas le juge ici. S'il était mon élève, je serais un peu féroce qu'il répondit à une table de recherche précomptes et disqualifie probablement la réponse. Juste dire qu'il peut vouloir voir; Le calcul d'un tamis complet serait surcharger de l'entrée est "100", il ne voudrait donc pas le faire à la volée, mais s'il peut précaliser la réponse la plus proche à "100", son runtime sera vraiment rapide.
@mmr: vraiment? Dans mes livres tamisant une table de premier tour est l'une des premières astuces pour optimiser un problème de choix. S'il était mon élève, je serais impressionné par l'ingéniosité!
@MMR & DAVID: J'ai posté du code ... Il s'agit d'une table des nombres premiers nécessaires à la vérification rapide des nombres premiers après (jusqu'à la place du plus grand nombre cible). Le seul premier choix codé requis est 2 - la table est ensuite construite de manière incrémentielle dans une boucle, en utilisant les valeurs précédemment calculées pour calculer les nouvelles. Il suffit d'inclure une table précalisée cependant serait boiteux / inacceptable IMHO, car cela ne rend pas vraiment l'algorithme "mieux" mais plutôt "muet mais rapide".
@MMR: +1 To David's Commentaire: Un étudiant qui résout que l'utilisation d'un tamis connaît probablement ses affaires. Ce n'est pas tricher et vous n'avez pas d'enseignement des affaires.
@ Wizardofodds-- vraiment? Un étudiant qui calcule les réponses à un problème chronométré à l'avance, puis fait référence à une table pour la réponse est dans l'esprit de la compétition? Comme @LUCERO souligne, c'est boiteux, car il est "muet mais rapide", et en tant qu'enseignant, oui, je disqualifierais cela. Peut-être que votre style d'enseignement est pourquoi j'ai une telle période difficile à trouver des personnes formées et compétentes pouvant écrire un code décent, mais un temps vraiment facile à trouver des perroquets qui ne peuvent pas penser à leurs pieds.
+1 pour Miller-Rabin. De l'article, vous liez à: "Si N <4 759 123,141, il suffit de tester A = 2, 7 et 61".
@MMR: Je ne dis pas qu'il devrait y avoir une table de nombres premiers codée dur au codement au code, juste qu'ils devraient courir un tamis au début de la session chronométrée. Si vous avez donné dites 100 cas de test et que vous avez dit de déterminer les réponses à tous les cas le plus rapidement possible, pourquoi n'est-ce pas? Que gagnez-vous en ne transmettez-vous pas d'informations entre les cas de test? En dehors de la curiosité, étiez-vous d'accord avec une solution identique aux opérations, mais qui met également en cache si chaque nombre est prime une fois que cela a été calculé?
@ David-- Oh ouais, c'est totalement raisonnable. J'étais hypothétiquée à propos de passer à la prochaine étape, à propos de la cuisson. Je dis simplement que ce serait facile à faire une fois que le tamis avait été calculé, mais que la cuisson ne serait probablement pas dans l'esprit de la compétition . Nous sommes donc en accord et ce fil est long parce que je peux discuter avec une souche :)
Pour vous tous ... Oui, cela aurait été autorisé. Il y avait des problèmes graves avec la manière dont les questions ont été distribuées sur lesquelles des classes que vous aviez prises et une réponse raisonnable suffisamment rapide était acceptable. Mon partenaire et moi avons discuté de quelque chose comme ça si nous n'avions jamais entendu le terme technique, mais nous pensions que le calcul de l'avance d'avance aurait pris le même temps. (Ou suis-ce que je manque quelque chose?) Avec tous les autres Tweaks que vous avez donnez, cependant, je pourrai le faire fonctionner. Merci beaucoup à vous tous !!!
@Sipsop: La différence est que le tamisage est beaucoup plus rapide que de tester chaque numéro de primalité. Pensez au nombre d'opérations que chaque méthode prend pour répertorier tous les nombres premiers de dire 1 à 1000.
@ Obtenez la racine carrée d'un numéro puis boucle jusqu'à ce que la racine carrée élimine même les nombres et voir s'il n'est pas divisible
La grande inefficacité Voici votre méthode de test de choix Prime . Prenez un réflexion sur le nombre de fois où il devra tester les mêmes nombres et se concentrer sur la manière dont on pourrait tirer parti des structures de mémoire afin d'éviter certains des calculs répétés.
Oui. Après avoir lu ce post, c'est exactement ce que je souhaite m'avoir eu lieu pendant la Comp.
Votre chèque prime est très inefficace. En fait, vous n'avez pas besoin de revérifier des multiples de nombres déjà vérifiés. Ainsi, lorsque vous vérifiez% 2, vous n'avez pas besoin de vérifier le% 4.
Pour savoir si un numéro est un premier, il vous suffit d'essayer de le diviser par tous les nombres premiers connus jusqu'à atteindre la racine carrée du nombre à vérifier. Faire cela réduit considérablement le nombre de divisions considérablement: si votre application dispose d'une liste des primes de 2 .. ~ 44721 (par exemple calculée en tant qu'élément de préparation), vous pouvez vérifier tous les chiffres jusqu'à 2000000000 assez rapidement. P>
En outre, vous devez d'abord vérifier les plus petits des deux permutations (par exemple, la première vérification de votre échantillon 13, puis 31). P>
EDIT: STROPT> P> P > Voici un échantillon que j'ai rapidement mis en place dans C # (vous devrez faire quelques modifications syntaxiques mineures pour le faire courir sur Java, mais j'avais juste un compilateur C # à la main): P> public static long reverse(long value) {
long result = 0;
while (value > 0) {
result = result*10+(value%10);
value /= 10;
}
return result;
}
public static long[] knownPrimes = new long[1000000];
public static int knownPrimeCount = 0;
public static bool isPrime(long value) {
// we loop through all already known primes and try to divide by those (sieve sort of)
for (int primeIndex = 0; primeIndex < knownPrimeCount; primeIndex++) {
long primeToCheck = knownPrimes[primeIndex];
if (value % knownPrimes[primeIndex] == 0) {
// can be divided by the given prime -> not a prime
return false;
}
if ((primeToCheck * primeToCheck) > value) {
// square exceeds the value -> is a prime, no more checks needed
return true;
}
}
// if we come here, we've run out of primes to check against, and therefore we should indicate this as error
throw new ArgumentException(string.Format("{0} is too large to be checked against known primes", value), "value");
}
public static void Main(String[] args){
long loop = 2000000000;
long n = 1999990000;
// first we initialize all the primes we may be needing for the final computation
knownPrimes[knownPrimeCount++] = 2;
for (long i = 3; true; i++) {
if (isPrime(i)) {
// store the new prime
knownPrimes[knownPrimeCount++] = i;
if ((i * i) > loop) {
break; // we have all the primes we need now
}
}
}
// now we try to find matches
for (long i = n; i <= loop; i++) {
long reversed = reverse(i);
if ((reversed <= i) && isPrime(reversed) && isPrime(i)) {
Console.WriteLine("{0} <-> {1}", i, reversed);
}
}
Console.WriteLine("#");
Console.ReadKey(true);
}
Merci. C'est une bonne idée et je vais travailler sur ma propre version. Je n'avais pas pensé à garder chaque chef d'avocat trouvé jusqu'à présent et à diviser par ce qui y est. PS ... Votre nom == Bon groupe
@Sipsop, merci pour vos commentaires. Notez que, dans mon cas, "mon" nom est réellement emprunté à l'un de mes chevaux, celui de l'avatar qui est. Il est un étalon espagnol pure de 9 ans (pré: en.wikipedia.org/wiki/andalusian_horse). ;-)
en utilisant Biginteger.isprobableprime (certitude) et biginteger.nextProbableprable () peut réduire considérablement le nombre de cas dont vous avez besoin pour vérifier assez efficacement
que je crois aurait été bouse, mais si cela fonctionne, cela aurait été acceptable, je suppose. mais j'avoue que je n'ai pas pensé à utiliser cette classe
Je n'ai pas fait cela auparavant, mais voici quelques choses qui me viennent à l'esprit.
Si votre Squareroot est un entier, le nombre n'est pas amorifique
Si le numéro se termine dans un 0,2,4,5,6, ou 8, il n'est pas prime / sauf 2 lui-même
Numéro peut être divisé par 3 si la somme desdigits est divisible par 3 et par 9 si la somme est 9.
Je ne sais pas que les tests de Wether pour ces choses vous aident, au moins le test du Squareroot devrait vous aider, car vous devez le calculer quand même et vous pouvez déjà être fait.
Oh et biençoir Votre efficacité augmentera beaucoup si vous faites quelque chose comme un test de primalité Miller-Rabin http://en.wikipedia.org/wiki/miller-rabin_primality_test . Votre test actuel doit seulement être fait dans les cas qui ne sont pas certains.
Le gars qui l'a résolu dans la compétition (qui était une personne âgée qui montre la disparité entre les niveaux de questions ici, c'est que cela semblait de loin le plus facile et le reste n'avait aucune place à donner aux personnes dans des cours aussi bas). Je vérifiais la voie à beaucoup de cas beaucoup trop de fois que cela ressemble.
Une autre amélioration de la vitesse que vous pouvez créer dans Pour accélérer la méthode principale est de modifier votre boucle pour contrôler certains numéros composites, déroulant certaines itérations dans une séquence de tests. Le plus simple consiste à tester 2 en dehors de la boucle, puis à tester des nombres impairs ( 2 * i + 1 ). Un peu plus complexe est de tester 2, 3, puis 6 * i ± 1 . Vous pouvez continuer à étendre cette approche, à tester les premiers n premiers, puis à boucler le four p n # * i + j , où p n # est le premier Primordial (le produit des premiers nombres premiers) et J est un entier positif inférieur à et coprime à p n #.
Prime , vous pouvez commencer par un Test premier probabiliste et test à l'aide d'un test déterministe plus lent uniquement pour les cas que le test probabiliste ne peut pas déterminer.
En ce qui concerne les premiers conseils ... Je pense que je comprends cela en théorie, mais vous disiez essentiellement que cette méthode serait éteinte les cas les plus probables? Désolé si ce n'est pas tout, mais la première chose primordiale est nouvelle pour moi.
@SIPSOP: Il saute des multiples des premiers nombres premiers. Notez comment 2 * i + 1 saute même des numéros, et 6 * i ± 1 passe des multiples de 2 et 3. La page Wikipedia sur les tests de primalité ( EN.Wikipedia.org/wiki/primality_test ) a des exemples.
encore plus rapide que tout cela utilise le Miller-Rabin Test. C'est un test probabiliste et a donc un certain niveau d'erreur; Cependant, le test fonctionne plusieurs fois, ce qui rétrécit cette erreur aussi petite que nécessaire (50 suffit souvent pour les applications commerciales).
Pas en Java, mais Voici une implémentation rapide dans Python que j'ai préparé.
@outis ... Je vois ce que vous dites c'est une petite astuce soignée que je dois dire. Merci pour ça.
@graham ... aussi cool je lis un article sur le test que vous avez mentionné parce que je pense que j'ai compris le gist de celui-ci des commentaires que vous avez rendus Python ressemble toujours à la grecque pour moi. Je sais que tout le monde dit que c'est l'une des langues plus simples à ramasser mais pour une raison quelconque Java et C ++ semblent toujours plus lisibles pour moi. Quoi qu'il en soit, oui, ce aurait été un meilleur moyen de le faire. Merci encore à vous tous ceux qui m'ont donné des conseils que j'ai appris beaucoup de ce conseil. Je ne peux pas pour mes structures de données et mes algorithmes de classe à l'automne !!!
L'option la plus simple serait utile d'utiliser une bibliothèque de grand entiers existante. Il n'aura pas de bugs, et il fournira toutes les fonctions de support.
Si vous écrivez votre propre implémentation (c'est-à-dire pour une mission), je vous recommanderais de travailler à partir d'un algorithme de code pseudo dans un livre afin que vous compreniez Ce que vous faites.
Cela étant dit, l'une des méthodes les plus simples consiste à utiliser Jacobi et Legendre, et comparer pour l'égalité. Je viens de soumettre une cession pour le cryptage RSA. Voici ce que j'ai fait pour une précision unique, mais les algorithmes sont généraux et travaillent également pour plusieurs entiers de précision. performance est très bon, même avec de grands nombres.
@david Obtenez la racine carrée d'un numéro puis une boucle jusqu'à ce que la racine carrée élimine même les nombres et voir s'il n'est pas divisible
Notez que pour un problème tel que celui-ci, la grande variété de réponses peut être combinée de différentes manières.
Cette question semble être hors sujets car il s'agit d'une question de la théorie du nombre. Essayez math.stackexchange.com.