How to define the largest prime number within a given number?

Question

For example, you give the number 100 and the highest prime number within 100 is 97. How can I program this?

"Write the maior_prime function that takes an integer number greater than or equal to 2 as parameter and returns the largest prime number less than or equal to the number passed to the function

Note that

• maior_primo(100) must return 97

• maior_primo(7) must return 7

Hint: write a function éPrimo(k) and loop through the numbers to the given number checking whether the number is prime or not; if so, store in a variable. At the end of the loop, the value stored in the variable is the largest prime found."

That’s the question. Can you help me? I did some tests but they don’t make any sense. Follow one of the tests:

def maior_primo(p):
    while p >= 2:
        i = p - 1
        p % 1 == 0
        return p


def éPrimo(k):
    i = 2
    é_primo = 0
    while i < k:
        if k % i ==0:
            break
        else:
            i = i+1
    if i == k:
        é_primo = False
        return False
    else:
        é_primo = True
        return True

Answer 1

UPDATE: Anderson Carlos Woss has a great answer about Crivo, answered a month before mine: /a/206144/64969

I was a member of the Programming Marathon team at my college. We were the Balloon Collectors, from UECE. And cousins were almost constant during the Marathon issues, so we needed something fast, practical and efficient, very efficient.

The algorithm that we used to calculate prime numbers was the Sieve of Eratosthenes. Why was he efficient? Because he calculated all cousins less than or equal to n in a time of o(n log log n); and only needed to do this once, we could store this calculated value at the beginning of the program and use it further. I also need to point out that the Sieve requires memory o(n), so it can only be used for small numbers (like 700 million in C, maybe 100 million in Python, for example).

How does this algorithm work? Well, it works by marking the knowingly raw positions/composite numbers of a vector based on the primes it discovers. At the end of the Sieve, all unmarked positions remaining are known prime numbers.

Using the resulting prime vector to calculate the largest prime smaller than n

Suppose I have a vector called numero_eh_primo boolean. He needs to have at least n + 1 positions to work the Sieve. Obviously the Sieve has already rotated and we have this vector filled as follows:

• numero_eh_primo[i] is true if i for primo
• numero_eh_primo[i] is false if i is composed

To find out which prime is smaller than or equal to n, just go through the vector from n, decreasing a unit if the position is false and returning the first index found if the value is true.

Applying memoisation

If I have enough memory, I can apply a memoisation to make future consultations to the same number n constant order. For this, I need an auxiliary vector called maior_primo_menorque, that will return the largest prime greater than or equal to the index passed. For example: maior_primo_menorque[100] returns 97 when completed.

How to know if the value is not filled in? Simple, if null. If null, how to fill in? Well, let’s go to the memoization algorithm:

def get_maior_primo(n):
    if maior_primo_menorque[n]:
        return maior_primo_menorque[n]
   else:
        if numero_eh_primo[n]:
            maior_primo_menorque[n] = n
            return n
       else:
            maior_primo_menorque[n] = get_maior_primo(n - 1)
            return maior_primo_menorque[n]

The Sieve of Eratosthenes

So far I only said that I used the Sieve, but at no time I talked about how this Sieve works. Come on.

The Sieve begins with a vector with n + 1 positions, all set as a priori truth (ie, are possible primes). So, we disregard the numbers 0 and 1, marking them as false. After that, we go through the vector sequentially, until we find an index that is set as truth. At this point, we find a true cousin, so we should mark all its multiples as false; after marking the multiples as false, we go back to the vector sequentially.

def crivo(n, vetor_crivo_inicializado_como_true):
    vetor = vetor_crivo_inicializado_como_true
    vetor[0] = False
    vetor[1] = False

    for i in range(2, n + 1):
        if vetor[i]:
            # achou um primo, vamos marcar todos os múltiplos relevantes
            marcar_multiplos(n, vetor, i)

def marcar_multiplos(n, vetor_crivo, primo):
    for i in range(primo*primo, n + 1, primo):
        vetor_crivo[i] = False

Note the optimization of starting to mark multiples from the square of the prime: every multiple of this prime with another value has already been marked in a previous step. For example, with prime found 5, I have already marked the numbers 10 (multiple of 2), 15 (multiple of 3) and 20 (multiple of 2), the first composite number being the square of 5, 25.

The @LINQ gave me the tip to do a MCVE, I’ll send one as soon as possible

Answer 2

You can use the function created by Miguel in the post cited in the comments:

Code1:

def maior_primo(n):
    for num in reversed(range(1,n+1)):
        if all(num%i!=0 for i in range(2,num)):
            return num

Output1:

maior_primo(100) 
>>>97

---

Or you can use this function that I created, trying to make the process more intuitive and facilitate your understanding:

Code2:

def maior_primo(n):

    primos = []
    for i in range(n):
        c = 0
        for j in range(n):
            if i%(j+1) == 0: 
                c += 1
        if c == 2:
            primos.append(i)

    return(max(primos))

Output2:

maior_primo(100)
>>> 97

---

The idea behind it is as follows:

1. For each number from 1 to the number entered by the user when calling the function:
2. Check that the rest of the division of that number by the numbers from 1 to itself is equal to 0.
3. If equal to 0, add 1 to the counter.
4. If at the end of the iterations the counter is with the value 2, that means that the number is divisible only by 2 numbers in the loop from 1 to itself; that is, it is a prime number.
5. If the number’s prime, I’ll keep it on a list called primos
6. After testing all the numbers in the range
7. I will return to the user the highest value existing in the list primos.

This value will be the largest prime number in the range from 1 to the number inserted.

Answer 3

Hello,

I made a code to decrease the use of other libraries. Follows:

def maior_primo(n):
k = n        
while k > 1 and é_primo(k)==False:
    k = k - 1
return k

def é_primo(k):

primo = True    
div = 2

while k>div:
    
    if k % div == 0:
        primo = False
    div = div + 1
    
return primo

I hope it helps! Sincerely yours,

Answer 4

From what I understand from your statement, you want to implement a code that is able to display the greater prime number less than or equal to the number "n".

To resolve this issue you can use the following code:

def maior_primo(n):
    for c in range(n, 1, -1):
        if primo(c):
            return c


def primo(m):
    i = 1
    cont = 0
    while i <= m:
        if m % i == 0:
            cont += 1
        i += 1
        if cont > 2:
            return False
    return True


num = int(input('Digite um número inteiro maior que "1": '))

print(f'O maior número primo menor ou igual a "{num}" é: {maior_primo(num)}')

When we executed this code we received the following message: Digite um número inteiro maior que "1":. Right now we must enter an integer number greater than 1 and press enter.

From that moment the value is passed as parameter to the function maior_primo(). Getting there, the block for will iterate - as many times as necessary - on the range(n, 1, -1). In each of these iterations the block if will ask the function primo() if the value of c is in fact a prime number. So the function primo() shall calculate the divisors of c and if the number of divisors is equal to 2, will send the value True in response to the block if of function maior_primo(). Otherwise it will send False in response.

If the if of function maior_primo() receive False as a response to the function primo(), o will terminate the current iteration and execute the next one. If the if of function maior_primo receive True as a response to the function primo(), will be shown the return function and script will be automatically terminated.

Note:

For the fact of the block for, of function exibir_primo(), scroll down the range from the greater value - n - and terminate its execution shortly after finding the first cousin, such code is very efficient. Therefore, it will only execute the iterations that are exclusively necessary to find the first cousin. After it finds the first cousin, immediately it is displayed the return and, also, it is terminated the execution of the script.

Let’s test the code?

Example 1

Typing in the value 7, we will receive as an exit:

O maior número primo menor ou igual a "7" é: 7

In this case the input was a prime number - 7 - and the exit was the largest prime number equal to 7.

Example 2

Typing in the value 100, we will receive as an exit:

O maior número primo menor ou igual a "100" é: 97

In this case the input was a non-prime number - 100 - and the exit was the greater prime number less than 100, which in this case is 97.

Summary:

This code is able to calculate and display the greater prime number less than or equal to the number "n".

Answer 5

I found a way that I imagine to be simple and effective, without using it or things like:

def maior_primo(n):
div=1
uau=True   
cont=0
while div <=n and uau:
    if n%div== 0:
        cont=cont+1  
    if cont>=3:
        cont=1
        n=n-1
        div=1
    if cont==2 and n==div:
         uau=False   
    div=div+1
return n

I hope it will be useful.

Answer 6

I made a small change to @dot.PY’s code, as testing with 101 as the input number, the return for the highest prime was 97 - when the highest is 101 itself. See if it makes sense:

def maior_primo(entrada):
primos = []
for inc in range(entrada + 1):
    cont = 0
    for jinc in range(entrada + 1):
        if inc % (jinc + 1) == 0:
            cont += 1
    if cont == 2:
        primos.append(inc)
return(max(primos))