High Speed Prime Numbers Calculation

Introduction

I spend a lot of time, making programs capable of coming out with a large collection of prime numbers, for any use.

Let’s assume all of you know what a prime number is. The usual way for programs to calculate a number of prime numbers is collecting prime numbers one number at the time, calculating the next prime number, adding it to the previous list.

2 Is prime number, because it’s divisible only by itself and 1.
List is now {2}.
3 Is prime number, because it’s divisible only by itself and 1.
List is now {2, 3}.
4 Is not a prime number, because it’s divisible by 2, the 0th item of the list.
5 Is prime number, because it’s divisible only by itself and 1.
List is now {2, 3, 5}.
6 Is not a prime number, because it’s divisible by 2, the 0th item of the list.
7 Is prime number, because it’s divisible only by itself and 1.
List is now {2, 3, 5, 7}.
8 Is not a prime number, because it’s divisible by 2, the 0th item of the list.
9 Is not a prime number, because it’s divisible by 3, the 1st item of the list.
10 Is not a prime number, because it’s divisible by 2, the 0th item of the list.
And so on...

I’m not dividing the number 10 with other numbers whether they are or not prime number, because, there’s no use doing it. There’s no use on dividing a number by 2 and by 4, because 4 is 2 times 2, 6 is 2 times 3, and so on.

An appropriate algorithm to do this would be:

ArrayList primeNumbers = new ArrayList();

for(int i = 2; i < 100; i++)
{
    bool divisible = false;

    foreach(int number in primeNumbers)
        if(i % number == 0)
            divisible = true;

    if(divisible == false)
        primeNumbers.Add(i);
}

It works, and I do it fast. For each number for 2 to 100, it's dividing lots of times. If you are trying to get 100,000 prime numbers, the thing gets messy. But I am happy making my programs faster, improving its mechanisms, gaining in memory, writing them on assembler!, and that sort of things. But just then I found the The Sieve of Eratosthenes that made me open my eyes. This method, works as follows:

Write down the numbers 1, 2, 3, ..., n. We will eliminate composites by marking them. Initially all numbers are unmarked.
Mark the number 1 as special (it is neither prime nor composite). Set k=1. Until k exceeds or equals the square root of n, do this:
1. Find the first number in the list greater than k that has not been identified as composite. (The very first number so found is 2.) Call it m.
2. Mark the numbers 2m, 3m, 4m, ... as composite. (Thus in the first run, we mark all even numbers greater than 2. In the second run, we mark all multiples of 3 greater than 3.) m is a prime number. Put it on your list.
3. Set k=m and repeat.
Put the remaining unmarked numbers in the sequence on your list of prime numbers.

You can try making this on your own. It’s really easier and faster. Because you’re not dividing, you are just jumping equal numbers of spaces.

So I figured, if this method makes it easier for me, what could it make for a machine!? I had all I needed, so I started programming it. I’ve had a sheet of paper (an ordered array of booleans), and the jumping action… the for() statement!!! The results were amazing. I’ve calculated the first 3,000,000,000 numbers and distinguished them into primes and composites in just 10 minutes! Something impossible with the previous algorithm. The only difficulty is that you will need a huge memory, to go over this number. Obviously, this method, consumes lots of memory, but it’s a great way of getting fast the first hundreds of millions of prime numbers. So, you can go on with some other algorithm, working on disk, or something like that.

So, no more preambles, here's the code:

using System.Collections;

int topNumber = 1000000;
BitArray numbers = new BitArray(topNumber, true);

for(int i = 2; i < topNumber; i++)
    if(numbers[i])
    {
        for(int j = i * 2; j < topNumber; j += i)
            numbers[j] = false;
    }

int primes = 0;

for(int i = 1; i < topNumber; i++)
    if(numbers[i])
    {
        primes++;
        //Console.Out.WriteLine(i);
    }

Console.Out.WriteLine();
Console.Out.WriteLine(primes + " out of " + topNumber + " prime numbers found.");
Console.In.ReadLine();

//Tnx <A href="" target=_blank>Bistok</A> for your help!

I would hardly recommend you that you do not uncomment the Console.Out.WriteLine line, it really slows it all down, and that’s not the point of all these.

If you have a good machine and you make it to calculate a really big number of primes, please let me know, and if any of you has any suggestions either.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

About the Author

Mariano Abdala

Web Developer

Argentina

Member

My name is Mariano Abdala, I'm from Buenos Aires, Argentina. I've lived half a year in Rio do Janeiro, Brasil and a hole year in San Sebastián, Spain.

I've been developing software now for four years as a professional, but I'm doing these since I was a child. Actually, I run my first piece of software at the age of 9. It was a simple Logo code. You was asked to make decisions about a tale and the tale itself take form as the user plays it.

I'm really looking foward to discover and practice the 'state of the art' of software developing.

Article Top

Poor

Excellent

Add a reason or comment to your vote: x
Votes of 3 or less require a comment

Comments and Discussions

You must Sign In to use this message board. (secure sign-in)

Search this forum
	Profile popups Noise Layout Per page

MultiThreading prime calculation

mishamosherg

21:20 11 Oct '11

Made an app in C#, console level. It can find if 18446744073709551557 is prime in less than 30 seconds with an Intel Core i5 2410M Processsor (2.3 GHz, Dual-Core, HyperThreading).

Really memory efficient (doesn't use more than 2.5 MB of RAM in any case).

Comments in code and printings are made in spanish. Google can help to understand them Poke tongue | ;-P

And now, the code:

File PrimosApp.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
 
class PrimosApp
{
    static void Main(string[] args)
    {
        Console.Title = "Hecho por Elmer Miroslav Mosher Golovin";
        UInt64 num = 0;
        int opcion;
        opcion = Primos.Menu();
        while (opcion != 2)
        {
            Console.Clear();
            Console.WriteLine("Escriba el número que desea saber si es o no primo");
            num = ValidacionEntradas.EsUInt64();
            PrimosThreads.Verificar(num);
            Console.Clear();
            opcion = Primos.Menu();
        }
    }
}

File Primos.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
 
public static class Primos
{
    public static Byte Menu()
    {
        Byte opcion;
        Console.WriteLine("Bienvenido al programa Primos.");
        Console.WriteLine("Introduzca el número de la opción correspondiente para la realización de una\noperación. Seguidamente pulse INTRO.");
        Console.WriteLine("1. Verificar si un número es primo");
        Console.WriteLine("2. Salir");
    otravez: ;
        opcion = ValidacionEntradas.EsByte();
        if (opcion != 2 && opcion != 1)
        {
            ValidacionEntradas.MostrarMensaje("Introduzca una opción correcta.");
            goto otravez;
        }
        return opcion;
    }
}

File PrimosThreads.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;
 
class PrimosThreads
{
    public static UInt64 num, nummodd;
    public static char resp = 'S';
    public static bool terminado = false;
    public static void Verificar(UInt64 numm)
    {
        num = numm;
        UInt64 nummod = 2, primo, sqrt;
        sqrt = (UInt64)Math.Sqrt(num);
        if (num == 1 || num == 0)
        {
            Console.WriteLine("No es Primo");
        }
        else
        {
            primo = num % nummod;
            if (primo != 0 && nummod >= sqrt)
            {
                resp = 'P';
            }
            else
            {
                if (primo == 0 && num > nummod)
                {
                    resp = 'N';
                }
            }
            ++nummod;
            if (resp == 'S')
            {
                Thread Hilo1 = new Thread(PrimosThreads.HiloVerificacion1);
                Thread Hilo2 = new Thread(PrimosThreads.HiloVerificacion2);
                Thread Hilo3 = new Thread(PrimosThreads.HiloVerificacion3);
                Thread Hilo4 = new Thread(PrimosThreads.HiloVerificacion4);
                Hilo1.Start();
                if (num > 1000)
                {
                    Hilo2.Start();
                    Hilo3.Start();
                    Hilo4.Start();
                }
                while (resp == 'S')
                {
                    Thread.Sleep(500);
                }
                Hilo1.Abort();
                if (num > 1000)
                {
                    Hilo2.Abort();
                    Hilo3.Abort();
                    Hilo4.Abort();
                }
                Hilo1.Join();
                if (num > 1000)
                {
                    Hilo2.Join();
                    Hilo3.Join();
                    Hilo4.Join();
                }
                nummod = nummodd;
            }
            if (resp == 'P')
            {
                Console.WriteLine("Es primo");
            }
            else
            {
                Console.WriteLine("No es primo");
            }
        }
        if (resp == 'N' && nummod == 3)
        {
            --nummod;
            Console.WriteLine("Se puede escribir como el producto de los siguientes dos numeros:\n{0} x {1}", nummod, num / nummod);
        }
        else
        {
            if (resp == 'N' && nummod != 3)
            {
                nummod -= 2;
                Console.WriteLine("Se puede escribir como el producto de los siguientes dos numeros:\n{0} x {1}", nummod, num / nummod);
            }
        }
        resp = 'S';
        terminado = false;
        Console.ReadKey();
        GC.Collect();
    }
    public static void HiloVerificacion1()
    {
        UInt64 nummod = 3, primo, sqrt;
        sqrt = (UInt64)Math.Sqrt(num);
        while (resp == 'S' && terminado == false)
        {
            primo = num % nummod;
            if (primo != 0 && nummod >= sqrt)
            {
                resp = 'P';
            }
            else
            {
                if (primo == 0 && nummod <= sqrt)
                {
                    resp = 'N';
                }
            }
            nummod += 2;
        }
        if (terminado == true)
            goto fin;
        terminado = true;
        nummodd = nummod;
    fin: ;
    }
    public static void HiloVerificacion2()
    {
        UInt64 primo, sqrt, nummod;
        sqrt = (UInt64)Math.Sqrt(num);
        nummod = sqrt / 4 - 1;
        while (resp == 'S' && terminado == false)
        {
            primo = num % nummod;
            if (primo != 0 && nummod >= sqrt)
            {
                resp = 'P';
            }
            else
            {
                if (primo == 0 && nummod <= sqrt)
                {
                    resp = 'N';
                }
            }
            nummod += 2;
        }
        if (terminado == true)
            goto fin;
        terminado = true;
        nummodd = nummod;
    fin: ;
    }
    public static void HiloVerificacion3()
    {
        UInt64 primo, sqrt, nummod;
        sqrt = (UInt64)Math.Sqrt(num);
        nummod = sqrt / 2 - 1;
        while (resp == 'S' && terminado == false)
        {
            primo = num % nummod;
            if (primo != 0 && nummod >= sqrt)
            {
                resp = 'P';
            }
            else
            {
                if (primo == 0 && nummod <= sqrt)
                {
                    resp = 'N';
                }
            }
            nummod += 2;
        }
        if (terminado == true)
            goto fin;
        terminado = true;
        nummodd = nummod;
    fin: ;
    }
    public static void HiloVerificacion4()
    {
        UInt64 primo, sqrt, nummod;
        sqrt = (UInt64)Math.Sqrt(num);
        nummod = (sqrt / 4) * 3 - 1;
        while (resp == 'S' && terminado == false)
        {
            primo = num % nummod;
            if (primo != 0 && nummod >= sqrt)
            {
                resp = 'P';
            }
            else
            {
                if (primo == 0 && nummod <= sqrt)
                {
                    resp = 'N';
                }
            }
            nummod += 2;
        }
        if (terminado == true)
            goto fin;
        terminado = true;
        nummodd = nummod;
    fin: ;
    }
}

File ValidacionEntradas.cs

using System;
 
public static class ValidacionEntradas
{
    static int Posicion;
    static bool valorcorrecto;
    public static Byte EsByte()
    {
        Byte dato;
    otravez: ;
        valorcorrecto = Byte.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 8 bits sin signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static SByte EsSByte()
    {
        SByte dato;
    otravez: ;
        valorcorrecto = SByte.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 8 bits con signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Int16 EsInt16()
    {
        Int16 dato;
    otravez: ;
        valorcorrecto = Int16.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 16 bits con signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static UInt16 EsUInt16()
    {
        UInt16 dato;
    otravez: ;
        valorcorrecto = UInt16.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 16 bits sin signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Int32 EsInt32()
    {
        Int32 dato;
    otravez: ;
        valorcorrecto = Int32.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 32 bits con signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static UInt32 EsUInt32()
    {
        UInt32 dato;
    otravez: ;
        valorcorrecto = UInt32.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 32 bits sin signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Int64 EsInt64()
    {
        Int64 dato;
    otravez: ;
        valorcorrecto = Int64.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 64 bits con signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static UInt64 EsUInt64()
    {
        UInt64 dato;
    otravez: ;
        valorcorrecto = UInt64.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número entero de 64 bits sin signo. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Single EsSingle()
    {
        Single dato;
    otravez: ;
        valorcorrecto = Single.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número de coma flotante de 32 bits. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Double EsDouble()
    {
        Double dato;
    otravez: ;
        valorcorrecto = Double.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número de coma flotante de 64 bits. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Decimal EsDecimal()
    {
        Decimal dato;
    otravez: ;
        valorcorrecto = Decimal.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un número de coma flotante de 128 bits. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static Char EsChar()
    {
        Char dato;
    otravez: ;
        valorcorrecto = Char.TryParse(Console.ReadLine(), out dato);
        if (valorcorrecto == false)
        {
            ValidacionEntradas.MostrarMensaje("No ha introducido un caracter único. Inténtelo nuevamente.");
            goto otravez;
        }
        return dato;
    }
    public static void MostrarMensaje(string mensaje)
    {
        if (Console.CursorTop != 0)
            Posicion = Console.CursorTop - 1;
        Console.SetCursorPosition(0, Posicion);
        Console.Write(mensaje);
        Console.ReadKey();
        Console.SetCursorPosition(0, Posicion);
        Console.Write("                                                                              ");
        Console.SetCursorPosition(0, Posicion);
    }
}

My vote of 1

cocowalla

23:42 26 Aug '10

Nonsense
Sign In·View Thread·Permalink

My vote of 1

ilke can

6:31 25 Mar '10

Elementary stuff presented like sophisticated.
Sign In·View Thread·Permalink

The Best And Easy Of Prime Number Is

mehranrezaie

0:44 28 Oct '08

#include <iostream> using std::cout; using std::cin; void main() { inti,num,sum; cout<<"Enter Your Number\n"; cin>>num; for(i=2;i<num;i++) { sum=num%i; if(sum==0){ cout<<"your Number Isn't Prime\n"; break;}} if(sum!=0) Cout<<"Your Number Is Prime\n"; }
Sign In·View Thread·Permalink

LOL

baks256

4:09 31 May '07

is it a high speed algorithm? you must be kidding I advise you to use algorithms base on pseudoprime numbers. it is much more faster, besides, the probability of mistakes is very small.
Sign In·View Thread·Permalink	1.00/5 (1 vote)

Re: LOL

Mariano Abdala

4:22 31 May '07

I advise you to read previous topics, what you're talking about has being already replyed. Mariano, el estupefacto. `//TODO: Make this damn code work!`
Sign In·View Thread·Permalink

high speed prime numbers

prasofty

20:43 20 May '07

in this program i got prime no's below the give no: can u give me an idea .......... first 100 prime no; not below thwe 100 prime no?
Sign In·View Thread·Permalink

Re: high speed prime numbers

Mariano Abdala

1:03 21 May '07

Hi! Sure, I guess you could just uncomment this line `//Console.Out.WriteLine(i);` But I would suggest you to write them donw on a File, instead of printing them on screen. Greetings! Mariano, el estupefacto. `//TODO: Make this damn code work!`
Sign In·View Thread·Permalink

High Speed ?

amircorrtec

18:19 18 Feb '07

Hi I thnink it is more efficient than others but the problem is it is not able to find the biggest one. Don't try for infinity. Amir Ali
Sign In·View Thread·Permalink

Re: High Speed ?

Mariano Abdala

0:17 19 Feb '07

Do you have a better way of doing it? Mariano, el estupefacto. `//TODO: Make this damn code work!`
Sign In·View Thread·Permalink

I have a algorith plus quick that.

MauricioFox

20:44 22 Jul '06

and is the next:

All Prime Numbers are write whit the next formulate:

6n+1 or 6n-1 this is very easy to demostrate. but the problem is that all number generate with 6n+1 or 6n-1 are prime, later you need know if this is a prime number or no... well the solution is the next

example: we supose that M=6n+1 and we need know if this number M is or not prime.

for i=0 to i=M^(1/2)
if(M%i==0)then
return "this is no a prime"
return "this is a prime"

Smile | :)

MauricioFox

vi japi

Hmmmm......

Paul Conrad

20:28 11 Jul '06

There are faster algorithms for finding primes.
Sign In·View Thread·Permalink

Yet one more suggestion.

petrowi

11:21 20 Jun '06

A while back (10 years) I had an implementation in Turbo Pascal 7 (does anyone remember it? Smile | :)

) ) and it calculated the first 1bln primes in about a week on AMD K2 266Mhz/32Mb RAM machine.

Two things are applicable here: restructuring the bitmap and "sliding window".

What happens is you're keeping all the calculated values in order to reuse them. To reach 4bln you'd need 256Mb of memory... hmm 256Mb x 8bits = 2Gbits, but it's obvious that every even number is divisible by 2, so there is no need to store a bit for it. You can go further - in every 6 numbers 4 are not prime - 3 are divisible by 2, 2 are divisible by 3 and 1 is divisible by both 2 and 3. Going further doesn't make much sense - it gets too complicated and starts slowing down because of index calculations.
This way you wouldn't even need to "init" your array for the number 2.

Another thing you can do if you don't need all the calculated primes in memory, but just to output them:
If you output the maximum number you use to index the bitmap to check if your number is divisible by some prime you'll see it won't go too far. For 4bln it's around 63000 - the square of your largest found prime. You can split your bitmap into two bitmaps - one that holds the primes 2,3..sqrt(MAX_PRIME_EVER_TO_FIND) and another one that you calculate and output in a cicle (your "sliding window"), then repeat the cicle by assuming a different number to correspond to your sliding window's first element.

Sten

Yet another suggestion

montclaris

17:29 24 Jan '06

You could change the loop boundaries to improve complexity of your algorithm.
The inner loop could be set to begin at bound j = i*i instead of j = i*2. This is valid because at this point of the loop, any number below i has already discarded all its multiples. So given any number a below i, a*i is a multiple of a and was therefore discarded previously (loop invariant). There's no point discarding it once more.
Then, the upper bound of your outer loop could be improved by stopping the loop when condition i*i > topNumber is met. When i*i is above topNumber, the inner loop would generate its smallest multiple (j = i * i) > topNumber. After this point you would never enter your inner loop because of its upper bound, so better stop sooner than later.

Wheel Factorization

danielibarnes

12:06 11 Nov '05

Wheel factorization is much faster. See this example.
Sign In·View Thread·Permalink

False Primes

jmoral4

10:30 24 Aug '05

Perhaps I missed the point of this exercise but... the 'speedier' algorithm above returns false primes. It treats numbers like 9 and 15 as prime numbers. Perhaps I took the implementation too literally.

The first algorithm listed above seems to work correctly. I evaluated Int.MaxValue.

I happened to be researching Encryption algorithms and I decided to write a short Prime Number Generator after looking at how RSA encryption works.

Re: False Primes

Mariano Abdala

10:38 24 Aug '05

Hello jmoral4!

I tried the first 50 numbers by copying the code on the page and the result was:

1
2
3
5
7
11
13
17
19
23
29
31
37
41
43
47

16 out of 50 prime numbers found.

As you can see 9 and 15 aren't on the results. But it might be a bug somewhere. Would you please like to tell me exactly what you've done to get that numbers??

Thanks for the comments!

Mariano, el estupefacto. WTF | :WTF:

//TODO: Make this damn code work!

Re: False Primes

jmoral4

22:40 24 Aug '05

You're absolutely right, thanks. I must have made a mistake transcribing as I can't copy and paste between our internal and external networks. Makes a lot more sense now
Sign In·View Thread·Permalink

Re: False Primes

Mariano Abdala

3:45 25 Aug '05

No problem! Could happend to anyone. If you need some help on this or if you would like to use it on your work, let me know and I'll do my best to help you. Mariano, el estupefacto. `//TODO: Make this damn code work!`
Sign In·View Thread·Permalink

Re: False Primes

Member 2945082

7:09 13 Jan '09

I think that the second loop should also start with 2. Remember that all bits are initially set to true, but the ones that are set to false start from 4, so it appears that the first are all primes? Don't think so.. So either you set number[0] and number[1] to false, or you start the second loop from 2 instead of 1
Sign In·View Thread·Permalink

I've done something similar

Yan Yorga

2:47 15 Dec '04

I have no idea why I started doing it but I did.

My first step was the same as yours except I increment by 2 and I store the result of the division and if it is less than the next prime to divide by, the number being tested must be prime.

I then looked at eliminating numbers from a number line by 'stepping' in prime numbers. I realised that with this method if you are not starting from 0 you need to store the largest multiple of each prime that you have got to so you can resume later on OR you would have to divide n by each prime, round down the result and then multiply by the same prime. This gives you your new start point to begin stepping from.

I also considered changing the base and doing a 'step left' to eliminate sets of numbers but I don't know how to code that which is how I arrived here Smile | :)

Your arguement against using the faster probability method is that it is not definite. The only question you need to answer is can it eliminate numbers which are not primes faster than other methods. Then you can test the remaining possibilities with a definite algoritm. To perfect it you would need to find out where it becomes more efficient to stop eliminating numbers by doing more iterations and find out for certain.

I think the advantage of the first method is that it can be picked up at any point by just recording the last prime number that was used to divide by. It's only problem is you need to know all the prime numbers up to the square root of the number you are testing.

Re: I've done something similar

Mariano Abdala

4:23 16 Feb '05

Hi! Tnx for the comment. About the probability method, my intention never was to discredit it. I think it's great, but it can't be aplied to 'my' method.

I've been investigating a little more about what my application was capable of, and discover that most of those 10 minutes I talk about, the machine was swapping memory onto the HD. And about 10 SECONDS were really used to run the program algorithm. I did this program in C# as a way to probe that The Sieve Of Erastotenes was the best way of calculating ALL prime numbers in a computer. I think I've probe it right. To extend this program, it would have to be written maybe in assembler and run as much as possible into RAM and the rest of it into a HD o any large storage unit.

In fact, most of the time of the whole process is getting a place to storage the result and a little bit of it to run the algorithm. That's way, I think, most of developmet to extend the program would be destinated to program an efficient way to get space and storage the results.

Way did you get interested into calculating prime numbers? Are you working on something related to it?

Greetings.

Mariano, el estupefacto. WTF | :WTF:

//TODO: Make this damn code work!

One More Suggetion

Prashant Mishra

14:57 21 Oct '04

You can use binary search and increase the spead of alorithm.
Sign In·View Thread·Permalink

High speed? I think not.

Jörgen Sigvardsson

8:29 20 Aug '04

Your algorithm is ~~quadratic~~ [edit]n*log(n)-ish[/edit] in time complexity, and linear in space complexity. It's neither fast nor efficient for anything but very small prime numbers.

As pointed out earlier, have a look at the Rabin-Miller Prime Number Test[^]. It has logarithmic time complexity, and constant space complexity.

To find a prime number is easy using the test. Pick a number of the magnitude you'd like the prime number to have. Test the number using 20 something iterations. If the test says "No", subtract or add 1 to your number and do the test again. Repeat until prime number "probably" found.

--
Denn du bist, was du isst!
Und ihr wisst, was es ist!

Es ist mein Teil...?

Re: High speed? I think not.

|\/| /\ |Z ! /\ |\| []

8:35 20 Aug '04

So, that big algorithm, just give you 'probable prime numbers'? That efficiency! In fact, you could see these my way. If something is probable but not sure, you can have for sure that's gona fail. That's the point of a realy great LAW, the murphy's law. So thanks, but's no use on Rubin-Miller's for me. Mariano, el estupefacto. `//TODO: Make this damn code work!`
Sign In·View Thread·Permalink