There are many different algorithms to generate prime numbers and they're really interesting.
Check out this page for a whole lot of them: http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm
This one is a short simple algorithm which is not so efficient but still useful for general purposes(generates 10 million primes in a little more than 6 seconds on an AMD Dual core 2.6 Ghz)
First some information which will be useful to understand the algorithm:
1. Factors of a number "converge" to the square root of the number
e.g Let's say we have the number 1024:
The factors of 1024 are:
32*32=1024
16*64=1024
8*128=1024
4*256=1024
2*512=1024
1*1024=1024
As you'll notice as you go from bottom to the top, the factors converge towards the square root of 1024, i.e 32.
The point here that if we need to check if 1024 is a prime number, 1024 should not be divisible by any number from 1 up to 32 (sqrt(1024)). For example if we see that 1024 is divisible by 8 (1024=8*128), in order to save calculations we don't need to check that 1024 is divisible by 128.
2. Every number can be broken down into prime factors
e.g 345=3*5*23 (3,5,23 are all prime numbers)
This 2nd idea is more interesting. Since a number can be broken down into prime factors(which are smaller than the number itself), then if a number is a prime number, it should not be divisible by any prime number smaller than itself.
This means that to determine if a number is prime, we just compare it with a list of primes smaller than itself and see if it is divisible by any one of them. If it's not then it's prime.
These 2 ideas can be combined together to form the following idea:
If a number is prime, it should not be divisible by prime numbers starting from 2 up to the square root of the number.
For example to determine if 23 is prime:
sqrt(23)=4.796
Prime numbers before 4.796= 2,3
Is 23 divisible by 2? no
Is 23 divisible by 3? no
So 23, is prime and it's added to the primes list.
Here's some C code which illustrates the above concept.
//sniper11
#include <stdlib.h>#include <stdio.h>
#include <math.h>
#define PMAX 20000000 /*max number of primes to generate*/
int n;
int c=0;
unsigned int primes[PMAX]; int primeptr=0;
int add_prime(int i)
{
primes[primeptr]=i;
primeptr++;c++;
}
int gen_primes()
{
int i,j,prime;
add_prime(2);//add 2 to the list
for(i=3;i<=n;i+=2)//skip even numbers
{
prime=1;
int maxfactor=sqrt(i);
for(j=1;j<primeptr;j++){
if(primes[j]>maxfactor)
break;
if(i%primes[j]==0){
prime=0;
break;
}
}
if(prime==1){
add_prime(i);
}
}
}
int output_primes()
{
int i;
for(i=0;i<primeptr;i++)
{
printf("%d\n",primes[i]);
}
}
int main()
{
printf("Number of primes to generate: ");
scanf("%d",&n);
gen_primes();
printf("Count: %d\n",c);
output_primes();
}
nice man
ReplyDeletethank you very much
Say not all that you know, believe not all that you hear...................................................
ReplyDelete噴泉的高度,不會超過它的源頭。一個人的事業也是如此,它的成就絕不會超過自己的信念。 ....................................................
ReplyDelete大奶妹貼圖區0204性影片觀賞露點自拍淫婦女生如何自慰色情站成人笑話av激情網愛視訊美女淫蕩av成人色情電話辣妹視訊聊天性關係情色vcd自慰圖淫美成人論壇台灣色情論壇成人聊天室自拍裸女貼圖視訊成人免費a片影片av成人網成人色情色情台灣辣妹小穴太太陰毛色情訊息裸女自拍色情影片a片論壇性愛技巧美女脫胸罩性情色天堂av寫真色情視訊聊天做愛視訊成人影片床上戲情色聊天網火辣情色台灣女優性愛秘笈台灣av女優手淫自慰影片
ReplyDelete