Comment vérifier si un nombre est premier ou non (Algorithme utilisant la force brute)

Question

J'ai conçu un algorithme qui prend une entrée et vérifie si un nombre est premier ou non. Est-ce correct?

1)Input num 
    2)counter= num-1 
    3)repeat 
    4)remainder = num%counter 
    5)if rem=0 then 
    6)broadcast not a prime.no and stop 
    7)decrement counter by 1 
    8)until counter = 1 
    9)say its a prime and stop 

Answer 1

Oui vous avez raison:

Voici un meilleur libellé psedo-code:

get Num from user 
get IsPrime = True 
for PFactor ranges from 2 to Num-1 do 
    begin block 
    if Num divisible by PFactor then set IsPrime = False 
    end block 
if IsPrime = True then display Num is prime 
else display Num is not prime 

Answer 2

Il est appelé algorithme am Sieve of Eratosthenes pour trouver nombre premier jusqu'à n nombre. La complexité asymptotique est O (nlog (logn)).

Le pseudo-code est quelque chose comme:

1. Créer un tableau à partir 0..MAX
2. À partir de 2, supprimer chaque multiple de 2 à partir du tableau.
3. Ensuite, revenez au début et supprimez tous les multiples de 3.
4. Répétez cette opération à partir du prochain numéro disponible au début du tableau.
5. Procédez ainsi jusqu'à ce que le carré du nombre que vous vérifiez soit supérieur à votre nombre maximal.
6. Enfin, compactez la matrice d'origine.

Ce tableau contiendra uniquement les nombres premiers jusqu'à votre nombre maximal. Vous constaterez que c'est vraiment très efficace. Tellement efficace que vous pouvez l'utiliser comme une méthode d'assistance pour déterminer si un nombre est premier ou non. Voulez-vous savoir si le nombre 105557 est prioritaire? Seulement prend 66 étapes.

code Ruby:

def sieve(max) 
    # Set up an array with all the numbers from 0 to the max 
    primes = (0..max).to_a 

    # Set both the first and second positions (i.e., 0 and 1) to nil, as they 
    # aren't prime. 
    primes[0] = primes[1] = nil 

    # Iterate through primes array 
    counter = 0 
    primes.each do |p| 
    # Skip if nil 
    next unless p 

    # Break if we are past the square root of the max value 
    break if p*p > max 
    counter += 1 
    # Start at the square of the current number, and step through. 
    # Go up to the max value, by multiples of the current number, and replace 
    # that value with nil in the primes array 
    (p*p).step(max,p) { |m| primes[m] = nil } 
    end 

    # Finally, return the compacted array. 
    puts "Solved for #{max} in #{counter} steps." 
    primes.compact 
end 

Pour vérifier si un nombre est premier ou non:

def prime?(num) 
    sieve(num).include?(num) 
end