I've found a way to generate all primes, now what do?

What are primes?

>>7696689
Put it in the pile next to the 10000000 other algorithms we know for generating primes?

>>7696697
Oh well, I figured people would have already come up with something so simple

Determine its computational complexity

Isn't that trivially easy to do? "A way to generate all primes" could just be a computer program that starts with i = 1, checks if it is prime and prints it if it is, then increments i and repeats indefinitely.

>>7697243
and what formula would you use to check if a number is prime?

>>7696689
Share it here? I'd like to see it.

All primes ONLY
or
All primes among all numbers?

>>7696697
Wrong. Prime generating algorithms that are 100% reliable are very few. And the ones that do are very complex and not useful because of the time it takes to even complete the prime generation for the bigger ones.

>>7696707
It is not simple.

>>7697221
Finally someone with a brain. OP, prove that yours is faster than the alternatives (as in it grows slower than others) and then get a honorary PhD from every Math and CompSci university in the universe.

>>7697243
That is useless. You are literally making useless calculations. And you are not generating primes, you are checking primes. Also, think about how much time it would take to find primes that have over 20 digits.

What you want to do is create a formula, prove that it only outputs primes and then make a computer program for it. These already exists but also have growth problems.

>>7697591
The simplest way is that for the number n you check if it can be divided by all primes smaller than n/2. But you can do better.

>>7697614
OP, if you are actually onto something don't show it here. Some fag will take your credit, assuming that you actually made something good.

>>7697623
Chemfag here; wouldn't a program that checked every number approaching infinity be less stress on a processor than a program that used algorithms in order to generate prime numbers?

>>7697618
All primes:
You start at number 2 and go through the numbers one by one. For each number you check if it's prime.

Where is my Nobel prize?

>>7697659
see
>>7697653

Let the math/cs fags tell us it's more complex than that

efficiencyfags are the worst

>>7697623
>"divided by all primes smaller than n/2"

>2014.99999...
>not going up to [math]\left \lceil{n} \right \rceil [/math] instead

>>7697623
>The simplest way is that for the number n you check if it can be divided by all primes smaller than n/2.
no, the factor couple reverses when you go beyond sqrt(n)

Sieve of erathostenes is n*log(n)

>>7699049
which is the best so far, is n*sqrt(n)

sieve is the way

>>7699052
what do you wanna do with your n*sqrt(n) ?

>>7699058
Checking, for each number, each factor up to sqrt(n) is n*sqrt(n)

File: evil laugh.gif (30KB, 300x369px) Image search: [Google]

30KB, 300x369px

>>7696689
Generate them. All of them.

OP here, I thought the thread died.

I checked the net, turns out my method is a variant of Sieve of Erasthothenes. I think it might be actually faster than what's available, but my coding is at script kiddie level, will try to implement it tho

>>7699246

int isPrime[N];

isPrime[0] = isPrime[1] = 0;
for (i = 2; i < N; i++) isPrime[i] = 1;
for (i = 2; i < N; i++) if (isPrime[i]) for (k = 2*i; k < N; k += i) isPrime[k] = 0;

>>7699252
Actually significantly slower. You only need to check prime factors less than or equal to sqrt(i) - after all, if one of i's factors is greater than sqrt(i), it must be multiplied by a factor smaller than sqrt(i).>>7699252
>int isPrime[N];

>isPrime[0] = isPrime[1] = 0;

>for (i = 2; i < N; i++)
> isPrime[i] = 1;
>for (i = 2; i < N; i++)
> if (isPrime[i])
> for (k = 2*i; k < N; k += i)
> isPrime[k] = 0;

>>7699270
What are you taking about? The sieve doesn't use the sqrt result. Running time's n*log(n)