You are not logged in.

- Topics: Active | Unanswered

It took me the last 24 hrs to generate approximately 14752000 primes

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

That is a lot of time.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

Do you have any suggestions to do it faster?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

What is the way that you are generating yours and what are you using as a language?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

Python(ya, its slow)

I am doing it this way

```
1. Load the previous list of primes(which I made six months ago)
2. Define the miller-rabin with k=7
3. Define the primality test which says whether or not a number is prime by checking whether it is divisible by all the primes which are in the list of primes upto the square root of the given number
4. Let n = the last prime in the list loaded
5. If n = 9999999999, terminate
6. Increment n by 1
7. If miller-rabin claims n to be prime, proceed to 8, otherwise goto 5
8. If the real primality test claims n to be prime, proceed to 9, otherwise goto 5
9. Write n in the file, goto 5
```

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

There are a couple of possible bottlenecks there.

First how fast is line 8? What method is being used?

Line 6, should be increment by 2.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

Ya, thats a. Good point

For 8, reffer 3

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

Two tests for primality are redundant.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

But the Miller rabin is done at first so as to save time

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

Yes but is it really saving time? I would totally go with the Miller - Rabin.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

If you would totally go with the miller-rabin, then how would you be sure whether the number you're going through is prime or not?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

There are things that are almost certainly true. They are so rare as to be impossible.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

bobbym wrote:

Okay, with k = 7 there was less than one chance in 16384 that it was making a mistake.

The risk is not worth it.

I am making a lot more primes than 16384

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

Supposing you doubled k? What do you think will happen?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

But still, what if I am one of those unlucky guys out of 100000000 who get a wrong result?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

By the way, last day at 12:30 at night I told Alokananda that her phone number is the sum of two primes. Than I told her that there are more than 113274 ways of representing that

She was perhaps shocked and said something which translates like "You do such things at night? Are you mad?"

Then she said, "Had it been any other girl, you would have driven them mad. Only because I am Alokananda, I am still not mad"

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

If you chose k = 14 then and if you generated 250 000 000 primes you should expect to only have 1 false prime in the list!

If you chose k = 21 you would need to generate 4 billion primes to expect to have 1 wrong!

But still, what if I am one of those unlucky guys

Do you know that you take a gamble like that everyday? You do not get unlucky.

Isn't it better to generate your list knowing there is an extremely tiny chance that one of them is false rather than generating no list that is perfect!

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

If I choose k=22, how much time would it take to complete upto 9999999999(10 digits)?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

how much time would it take to complete

That is another question. Right now we are dealing with mathematics and Agnishom's mind.

I would use k = 24 and it is extremely unlikely that there will be a false prime in your list.

Anyways, there are ways to now make sure there are no errors.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

What are they?

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

There are 455052511 primes less than 10 000 000 000. Your list is checked to see if it has that many, then you know there are no errors!

Now we can get to your last line which is possibly another error.

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

Error? Its my loop!

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

Excuse me, I meant 9.

Do you understand what I am saying about generating the primes?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline

9 says Write n to file, goto 5

'God exists because Mathematics is consistent, and the devil exists because we cannot prove it'

I'm not crazy, my mother had me tested.

Offline

**bobbym****Administrator**- From: Bumpkinland
- Registered: 2009-04-12
- Posts: 105,715

Okay, hold that for a second. Are you clear why you need only one test? Miller - Rabin will be enough?

**In mathematics, you don't understand things. You just get used to them.****If it ain't broke, fix it until it is.****No great discovery was ever made without a bold guess. **

Offline