I need help to formulate a prime number algorithm

-1

How is the algorithm that I have to write for a whole list of numbers save the first n ° cousin entered?

    
asked by nicolas 21.05.2017 в 19:20
source

2 answers

1

You have several options, the first that occurs to me is to go through the list and go testing if the each number is prime. To see if the number is prime you should check that the module always different from 0 to half of that number, something like this:

bool esPrimo = false;
for(int i = 0; i <= numero/2 || !esPrimo; ++i) 
     if(numero % i == 0)
          esPrimo = true;
    
answered by 21.05.2017 в 20:07
1

One of the fastest ... use the theorem below.

Theorem:

For all prime numbers p > 3, we have that p = 6k + 1 or p = 6k-1

Demonstration:

All the integers can be expressed exactly in one of the 6 possible ways: 6k, 6k + 1, 6k + 2, 6k + 3, 6k-2, or 6k-1 6k is divisible by 6, so it's not a cousin 6k + 2 is even, so it's not a cousin 6k + 3 = 3 (2k + 1) is divisible by 3, so it is not prime 6k-2 is even so it's not cousin Therefore, prime numbers have to be expressed in the form 6k + 1 or 6k-1. Note that not all numbers of that form are necessarily cousins.

Algorithm to determine if a number is prime

In many applications it is necessary to know whether a number n is prime or not. When n is very large, the known algorithms are very inefficient. Let's see the next one that is pretty quick for n not very big.

We will determine if a number n is prime, if some non-trivial divisor of n is found, you can make sure that n is composed, if no divisor is found then we conclude that n is prime. The algorithm is then based on an exhaustive search for a divisor of n. Next a pseudocode of the algorithm.

PRIME (x) // x > 3

if x mod 6 <> 1 and x mod 6 <> 5
    then return FALSE
r = SQRT(x)
i = 1
while 6*i-1 <= r do
    if x mod (6*i-1) = 0
        then return FALSE
    if x mod (6*i+1) = 0
        then return FALSE
    i = i + 1
    return TRUE

The Screen of Erastótenes

This is an algorithm known since ancient times, to determine all prime numbers from 2 up to a certain value n.

The algorithm is based on "marking" all the numbers that are multiples of some other minor. In the end, the numbers that "have survived such marking" of course, are cousins.

CRIBA_DE_ERASTOTENES (max)

for i = 2 to max do
    marked[i] = FALSE
for i = 2 to max do
    if marked[i] = FALSE
        then k = 2*i
while k <= max do
    marked[k] = TRUE
    k = k + i
return marked
    
answered by 21.05.2017 в 22:05