Nice, so you don't have to do any primality checking on those numbers?

Sweet, now i'm 30 seconds for 20mill.
2 min 53 secons for 100M

But how can i use it for much larger numbers...

Now, i am trying to sieve up to about 3.2GB (using 200MB of ram, how much memory should i be able to use? i have 256mb of ram, win2K).

I was thinking about 1. Using bit tables (how slow are they?) and 2. by only storing every second number. So i use half the space. (so then i can use 2*8*200M = 3.2G prime numbers).

I would need to search 1,094,967,296 numbers using trial division later.
That would take ages to do......

Now to search the whole thing, i would need 268,435,456 or 268MB, i only have 256mb... I'm going to see if i can find a comp with more memory...

How would i use the bitfields and the using every second number thing? (keep in mind, that i'm using vb, so bitshifts = mults).

Am i going quickly, given programming language and experience?

From,
Nice coder

[Edited by - Nice Coder on March 5, 2005 4:38:38 AM]

I've been thinking of making a little test program, so what it would do, is it would sieve up to x where x is a user specified number, before going and resolving queries.

Queries would be like: What is the closest prime number to x, is x prime, how many primes do you have, how fast did you search, what is a random prime number, multply x prime numbers together and give me the result, ect.

From,
Nice coder

Thats the sieve.

I'm trying to figure out how to use bittables, so t hat i can work with individual bits quickly....

Has anybody got any experience in this?

From,
Nice coder

Actually thats the type of thing that i tried. (really slow).

All that was needed was

open "C:\Outputfile.txt" for output as #1dim primes() as booleanredim primes(number)for x = 3 to numberif primes(x) = false then         print #1, x         for y = x to number step x         primes(y) = true         next yend ifnext xclose #1

Which searchesa bit over 1/2 million nums/second on my machine (p31ghz, 256mb ram).
Without needing to print off the data, it searches about 3/4-1 million nums/second.

Now, the thing that i'm a bit clueless about, is using bittables....

From,
Nice coder

I would get away from vb, but then again, i want a fast algorithm... (i also have a hate-hate relationship with my c++ compiler.) Also, wheres the challange of programming something fast in a language which has no optimisation and does everything the slow way? where a division can cost a few hundred times what it should cost, when every instruction needs to be carefully hand optimised....

Maybe i could make all k primes to 2^32? k being 101? (after i check the first few billion numbers, using a sieve that i'm still looking forward to building. As well as being completely stumed in how to build it...)

There would only be a very small chance that the numbers that are k prime over 101 are actually compisite.

I'm making a smallish adjustment to the sieve:
I'm going to make a sieve up to 200 million (assuming that nobody can tell me how to implement the changes, and i cannot figure out myself)
After that i go into a kprime mode where i use an isprime of the form

dim j as doublej = x * 0.5j += x * 0.3333333333333333333j += x * 0.2....isprime = (int(j) <> j)

Is this a nice way to do it?
From,
Nice coder

Quote:Original post by Telastyn
There was a recent breakthrough in India [?] regarding primality testing, which might help.

The new algorithm was developed by a team of researchers from Indian Institure of Technology. It is, however, an "accurate primality" algorithm rather than a speedy algorithm. Apparently, it generates primes with NO errors and is more oriented towards encryption and security paradigms.