This is a very vast subject. There are numerous methods to generate primes or to find out if a given number is a prime number or not. Here are a few of them. I strongly recommend you to search on the Internet for more elaborate information.
Brute Force
Test each number starting with 2 and continuing up to the number of primes we want to generate. We divide each numbr by all divisors upto the square root of that number. If no factors are found, its a prime.
Using only primes as divisors
Test each candidate only with numbers that have been already proven to be prime. To do so, keep a list of already found primes (probably using an array, a file or bit fields).
Test with odd candidates only
We need not test even candidates at all. We could make 2 a special case and just print it, not include it in the list of primes and start our candidate search with 3 and increment by 2 instead of one everytime.
Table method
Suppose we want to find all the primes between 1 and 64. We write out a table of these numbers, and proceed as follows. 2 is the first integer greater than 1, so its obviously prime. We now cross out all multiples of two. The next number we haven't crossed out is 3. We circle it and cross out all its multiples. The next non-crossed number is 5, sp we circle it and cross all its mutiples. We only have to do this for all numbers less than the square root of our upper limit, since any composite in the table must have atleast one factor less than the square root of the upper limit. Whats left after this process of elimination is all the prime numbers between 1 and 64.
Subscribe to:
Post Comments (Atom)
3 comments:
The following code uses two properties mentioned above
-> it stores the primes in an array and divides only by them
-> it just considers only odd numbers
#include< stdio.h >
int main()
{
int n;
printf("Enter the value of n\n");
scanf("%d",&n);
int a[n],i=0,number=3,flag=0;
a[0]=2;
i++;
int j;
while(i!=n)
{
flag=0;
for(j=0;j< i;j++)
if(number%a[j] ==0)
{
flag=1;
break;
}
if(!flag)
a[i++]= number;
number+= 2;
}
for(i=0;i< n;i++)
{
printf("%d\t",a[i]);
}
return 0;
}
Hope it has helped
**helper:)
int
Prime(int upperlim)
{
int *arr = NULL,i=0,start = 3,j=0,flag = 0;
arr = (int*)malloc(upperlim);
memset((char*)arr,0,upperlim);
arr[0] = 2;
i++;
while(start <= upperlim){
flag = 1;
for(j=0;j < i; j++)
{
if(start % arr[j] == 0){
flag = 0;
break;
}
}
if(flag)
arr[i++] = start;
start += 2;
}
for(j =0;j<i;j++)
printf("%d\n",arr[j]);
free(arr);
arr = NULL;
}
Thanks for the info. It is very helpful.
Regards
Educational site
Get jobs info at Educational site
Post a Comment