![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant.png)
Étant donné un entier positif N, la tâche est de trouver le NièmeNombre composé.
Exemples:
Saisir: N = 1
Sortir: 4
Saisir: N = 3
Sortir: 8
Approcher: Le problème donné peut être résolu en utilisant le concept de crible d’Eratosthène. Suivez les étapes ci-dessous pour résoudre le problème :
- Marquez tous les nombres premiers jusqu’à 105 dans un tableau booléen, disons que jesPrime[] en utilisant le tamis d’Eratosthène.
- Initialiser un tableau, disons matériaux composites[] qui stocke tous les nombres composés.
- Parcourir le tableau estPrime[] en utilisant la variable je, si la valeur de estPrime[i] est faux, puis insérez le nombre je dans le tableau matériaux composites[].
- Après avoir terminé les étapes ci-dessus, imprimez la valeur matériaux composites[N – 1] comme le NièmeNombre composé.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; #define MAX_SIZE 1000005 int NthComposite(int N) { bool IsPrime[MAX_SIZE]; memset(IsPrime, true, sizeof(IsPrime)); pour (int p = 2; p * p < MAX_SIZE ; p++) { si (EstPrime[p] == vrai) { pour (int i = p * p; i < MAX_SIZE ; je += p) EstPrime[i] = faux ; } } vecteur pour (int p = 4; p < MAX_SIZE; p++) si (!EstPrime[p]) Composites.push_back(p); retour Composites[N – 1]; } int main() { entier N = 4; cout << NthComposite(N); renvoie 0 ; } |
Java
|
importer java.util.*; classe publique GFG { public statique int NthComposite(int N) { int MAX_SIZE = 1000005 ; booléen[] IsPrime = nouveau booléen[MAX_SIZE]; Arrays.fill(IsPrime, true); pour (int p = 2; p * p < MAX_SIZE; p++) { si (EstPrime[p] == vrai) { pour (int i = p * p; i < MAX_SIZE ; je += p) EstPrime[i] = faux ; } } Vector pour (int p = 4; p < MAX_SIZE; p++) si (!EstPrime[p]) Composites.add(p); return Composites.get(N – 1); } public static void main(String args[]) { entier N = 4; System.out.println(NthComposite(N)); } } |
Python3
|
def NthComposite(N): EstPrime = [True]*1000005 pour p dans la plage (2, 1000005): si p * p > 1000005 : Pause si (EstPrime[p] == Vrai) : pour i dans la plage (p*p,1000005,p) : EstPrime[i] = Faux Composites = [] pour p dans la plage (4,1000005): si (pas IsPrime[p]): Composites.append(p) retour Composites[N – 1] if __name__ == ‘__main__’ : N = 4 imprimer (NthComposite(N)) |
C#
|
en utilisant le système ; en utilisant System.Collections.Generic ; classe publique GFG{ public statique int NthComposite(int N) { int MAX_SIZE = 1000005 ; bool[] IsPrime = nouveau booléen[MAX_SIZE]; Array.Fill(IsPrime, true); pour (int p = 2; p * p < MAX_SIZE; p++) { si (EstPrime[p] == vrai) { pour (int i = p * p; i < MAX_SIZE ; je += p) EstPrime[i] = faux ; } } List pour (int p = 4; p < MAX_SIZE; p++) si (!EstPrime[p]) Composites.Ajouter(p); retour Composites[N – 1]; } vide public statique Main () { entier N = 4; Console.WriteLine(NthComposite(N)); } } |
Javascript
Complexité temporelle : O(N + M * log(log(M)), où [2, M] est la gamme où le crible d’Eratosthène est effectué.
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts mathématiques importants pour la programmation compétitive avec le Mathématiques essentielles pour le cours CP à un prix adapté aux étudiants. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
