numéros de tempête

Pour que N soit un nombre stormer, le facteur premier le plus élevé de l'expression N^2+1 doit être supérieur ou égal à 2*N et doit être un entier positif.

Par exemple, 4 est un nombre stormer. Puisque 4*4+1=17 a lui-même le plus grand facteur premier 17 qui est supérieur à 8, c'est-à-dire 2*4.

Mais 3 n'est pas un nombre fort, car 3*3+1=10. Le plus grand facteur premier de 10 est 5, qui est inférieur à 6, qui est 2*3.

Dans ce problème, on nous donne un entier positif N, et notre objectif est d'imprimer les N premiers stormers.

Entrée : 4

SORTIE : 1 2 4 5

Voici les 4 premiers numéros du Stormer. 3 n’est pas un numéro Stormer, il n’est donc pas inclus.

Algorithme

• Trouvez le plus grand facteur premier du nombre (N^2+1) et stockez-le dans une variable arbitraire.

• Vérifiez si le facteur premier est supérieur ou égal à 2*N.

• S'il satisfait à la condition, il s'agit donc d'un numéro de stormer.

• Imprimez tous les numéros de stormer jusqu'à ce que i soit inférieur ou égal à N.

Méthode

Pour implémenter l'algorithme ci-dessus dans notre code, nous devons créer deux fonctions. Premièrement, pour connaître le facteur premier le plus élevé pour chaque cas et deuxièmement, vérifier s'il est supérieur ou égal à 2*N et continuer à imprimer le nombre si. c'est un numéro de stormer simultanément.

Pour découvrir le facteur premier d'expression le plus élevé (n^2+1) pour chaque nombre n −

• Nous diviserons le nombre par 2 jusqu'à ce qu'il donne le reste 0 et stockerons 2 dans primemax.

• Maintenant, n doit être un nombre impair à ce stade, nous allons donc parcourir une boucle for et parcourir uniquement les nombres impairs de i=3 à la racine carrée de n.

• Maintenant, stockez i dans primemax et divisez n par i pendant que je divise n. Lorsque je ne parviens pas à diviser n, augmentez-le de 2 et continuez.

• Si n est un nombre premier supérieur à 2, alors n ne deviendra pas 1 dans les deux premières étapes, nous stockons donc n dans primemax et renvoyons primemax.

La fonction suivante sera de vérifier si le numéro est un numéro stormer ou non. Si c'est le cas, nous l'imprimerons.

• Nous déclarerons une température variable à 0 pour compter les N premiers numéros de stormer.

• Commencez à partir de i=1 et effectuez une itération de boucle avant que la température ne soit inférieure à N.

• Vérifiez si (i*i+1) a le plus grand facteur premier supérieur ou égal à 2*i. Si la condition ci-dessus est vraie, imprimez i et incrémentez temp de 1.

La traduction chinoise de

Exemple

est :

Exemple

Vous trouverez ci-dessous l'implémentation de l'approche ci-dessus en C++ −

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int prime_factor(int n){ //for finding the maximum prime factor
   int primemax=0;
   while(n%2==0){ //if n is divided by 2 than we store 2 in primemax 
      primemax=2;
      n=n/2;
   }
   for(int i=3;i<=sqrt(n);i+=2){ // this is only for odd number 
      while(n%i==0){
         primemax=i;
         n=n/i;
      }
   }
   if(n>2){ // when n is prime number and greater than 2 
      primemax=n;
   }
   return primemax;
}
void stormer_number(int n){  //function to print first n stormer numbers
   int temp=0; // for counting the stormer number 
   for(int i=1;temp<n;i++){  // for iterating the all number 
      int check=(i*i)+1;  // for storing the (i*i)+1 value in check
      if(prime_factor(check)>=(2*i)){ //for checking the number if maximum prime is greater or equal to 2*i
         cout<<i<<" ";
         temp++;
      }
   }
}
int main(){
   int n=9;
   stormer_number(n);
   
   return 0;
}

Sortie

1 2 4 5 6 9 10 11 12

Conclusion

Dans cet article, nous essayons de résoudre le problème de l'impression des premiers numéros N Stormer.

Nous avons également appris à calculer les facteurs premiers d'un nombre. J'espère que cet article vous aidera à dissiper tous vos doutes sur ce problème.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!