algorithm to get all prime numbers?

Well, you can't find *all* of them no matter what you do, lol

But couldn't you just set a limit (ie. check numbers 2 - 5000) for primality, and for each have it check to see if ( the number being checked % an incremented number between 2 and "that number" ) = 0? Dunno otherwise, check wikipedia for some interesting "properties" of primes that may help.

is there an algorithm to find all prime numbers? im trying to write a program that does this, but my way of doing it doesnt work too well.Xeros606

I know the highest possible prime number has been established, but I also know it's been done only with great effort.quiglythegreat

Eh? The exact opposite was mathematically proven: there is no highest prime number. There are an infinite number of prime numbers.

Anyway, if you want a fairly easy algorithm to find a list of prime numbers, initialize a list with 2 as a known prime number, then starting at 3 and going up by 2 each time (since no even number greater than 2 is prime), check to see if the number under consideration is divisible by any of the numbers in the list of prime numbers. If not, you've found another prime number, so add it to the list.

Obviously you'll want to tell it to stop after some number of prime numbers, given that it will never stop finding prime numbers.

[QUOTE="quiglythegreat"]I know the highest possible prime number has been established, but I also know it's been done only with great effort.GabuEx

Eh? The exact opposite was mathematically proven: there is no highest prime number. There are an infinite number of prime numbers.

Anyway, if you want a fairly easy algorithm to find a list of prime numbers, initialize a list with 2 as a known prime number, then starting at 3 and going up by 2 each time (since no even number greater than 2 is prime), check to see if the number under consideration is divisible by any of the numbers in the list of prime numbers. If not, you've found another prime number, so add it to the list.

Obviously you'll want to tell it to stop after some number of prime numbers, given that it will never stop finding prime numbers.

[QUOTE="GabuEx"]

[QUOTE="quiglythegreat"]I know the highest possible prime number has been established, but I also know it's been done only with great effort.remmbermytitans

Eh? The exact opposite was mathematically proven: there is no highest prime number. There are an infinite number of prime numbers.

Anyway, if you want a fairly easy algorithm to find a list of prime numbers, initialize a list with 2 as a known prime number, then starting at 3 and going up by 2 each time (since no even number greater than 2 is prime), check to see if the number under consideration is divisible by any of the numbers in the list of prime numbers. If not, you've found another prime number, so add it to the list.

Obviously you'll want to tell it to stop after some number of prime numbers, given that it will never stop finding prime numbers.

http://primes.utm.edu/lists/small/1000.txt

[QUOTE="remmbermytitans"][QUOTE="GabuEx"]

Eh? The exact opposite was mathematically proven: there is no highest prime number. There are an infinite number of prime numbers.

Anyway, if you want a fairly easy algorithm to find a list of prime numbers, initialize a list with 2 as a known prime number, then starting at 3 and going up by 2 each time (since no even number greater than 2 is prime), check to see if the number under consideration is divisible by any of the numbers in the list of prime numbers. If not, you've found another prime number, so add it to the list.

Obviously you'll want to tell it to stop after some number of prime numbers, given that it will never stop finding prime numbers.

thepwninator

http://primes.utm.edu/lists/small/1000.txt

i tried that, but heres the problem. what if the number it checks is 121? it is not divisible by either 2, 3, 5, or 7, but it is also not a prime (it is divisible by 1, 11, and 121).Xeros606

Like I said, you have to check each number's divisibility with every prime number less than it that's less than or equal to its square root. I'm not sure why some are saying that you only need to check primes less than 10. :P

An algorithm you could implement is as follows:

L = {2}
i = 3

while (keepGoing)
{
    isPrime = true

    foreach (n in L such that n less than or equal to sqrt(i))
    {
        if (n divides i)
        {
            isPrime = false
        }
    }

    if (isPrime)
    {
        L = L union {i}
    }

    i = i + 2
}

Now you just need to define keepGoing.

Why not just implement the Sieve of Eratosthenes?

I remember doing that in BASIC, getting primes for an encryption algorithm.

Why not just implement the Sieve of Eratosthenes?

I remember doing that in BASIC, getting primes for an encryption algorithm.

Chavyneebslod

That algorithm works if you have a known upper bound for the size of prime number you're interested in, but it's basically useless if you want a program that can just keep going as long as you want it to.

[QUOTE="Xeros606"]i tried that, but heres the problem. what if the number it checks is 121? it is not divisible by either 2, 3, 5, or 7, but it is also not a prime (it is divisible by 1, 11, and 121).GabuEx

Like I said, you have to check each number's divisibility with every prime number less than it that's less than or equal to its square root. I'm not sure why some are saying that you only need to check primes less than 10. :P

An algorithm you could implement is as follows:

L = {2}
i = 3

while (keepGoing)
{
    isPrime = true

    foreach (n in L such that n less than or equal to sqrt(i))
    {
        if (n divides i)
        {
            isPrime = false
        }
    }

    if (isPrime)
    {
        L = L union {i}
    }

    i = i + 2
}

Now you just need to define keepGoing.

Sorry for being off topic, but what practical use does summation have? :?ghoklebutter

Prime numbers are often used for data encryption. Those digits/codes are harder to crack and thus a longer prime number is harder to brake.

I know the highest possible prime number has been established, but I also know it's been done only with great effort.quiglythegreat

is there an algorithm to find all prime numbers? im trying to write a program that does this, but my way of doing it doesnt work too well.Xeros606

[QUOTE="Chavyneebslod"]

Why not just implement the Sieve of Eratosthenes?

I remember doing that in BASIC, getting primes for an encryption algorithm.

GabuEx

That algorithm works if you have a known upper bound for the size of prime number you're interested in, but it's basically useless if you want a program that can just keep going as long as you want it to.

For my implementation, I just used MAX_INT as the cap :)xaos

I suppose that certainly works if you're a square who's using a data type with a maximum value. :P

[QUOTE="GabuEx"]

[QUOTE="quiglythegreat"]I know the highest possible prime number has been established, but I also know it's been done only with great effort.remmbermytitans

Eh? The exact opposite was mathematically proven: there is no highest prime number. There are an infinite number of prime numbers.

Anyway, if you want a fairly easy algorithm to find a list of prime numbers, initialize a list with 2 as a known prime number, then starting at 3 and going up by 2 each time (since no even number greater than 2 is prime), check to see if the number under consideration is divisible by any of the numbers in the list of prime numbers. If not, you've found another prime number, so add it to the list.

Obviously you'll want to tell it to stop after some number of prime numbers, given that it will never stop finding prime numbers.

Sweet Freakin' Jesus. . . .so many numbers. . .and it just keeps loading!:cry:

[QUOTE="xaos"]For my implementation, I just used MAX_INT as the cap :)GabuEx

I suppose that certainly works if you're a square who's using a data type with a maximum value. :P