Below is my prime generator, it works fine only thing it gives me 1 more prime than i want eg., if num=40, i need primes uptill 40 but it gives me 41 also...i want it to stop at 37.
It works fine with 90.
sample run
========
Enter the number:40
The primes are :2,3,5,7,11,13,17,19,23,29,31,37,41,Press any key to continue.. .

i suspect this has something to do with the starting off values.any pointer would be highly valued.

``````#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define  FALSE 0
#define  TRUE 1

int primes(int num);

int main()
{

int num;
printf("Enter the number:");
scanf("%d",&num);
printf("The primes are :");
(primes(num));
system ("pause");
return 0;
}

int primes(int num)
{

const int np=100;
int multiple[np]; /* multiples of primes */
int p[np]; /* primes upto sqrt(num) */
int i; /* index for primes saved */
int j; /* index of primes and multiple array */
int limit; /* upper index for primes less than sqrt(x) */
int plimsq; /* square of largest prime included so far */
int rootn; /* truncated sqrt(num) */
int dx; /* increment either 2 or 4 to avoid multiples of 3 */
int x; /* current candidate for prime test */
int prime;

p[1]=2;
p[2]=3;
p[3]=5;
i=3;

if (num<5)
for(j=1;j<=((num+1)/2);j++)
printf("%d,",p[j]);
else
{
for(j=1;j<=3;j++)
printf("%d,",p[j]);
x=5;
plimsq=25;
limit=3;
dx=2;
rootn=trunc(sqrt(num));
while(x<num)
{
x=x+dx;
dx=abs(dx-6);
if (limit<=i)
if(x>=plimsq)
{
multiple[limit]=plimsq;
limit=limit+1;
if (limit<=i)
plimsq=pow(p[limit],2);
}
prime=TRUE;
j=3;
while ((prime) && (j<limit))
{
while (multiple[j]<x)
multiple[j]=(multiple[j]+(p[j]*2));
prime=((x) != (multiple[j]));
j=j+1;
}
if(prime)
{
printf("%d,",x);
if(x<=rootn)
{
i=i+1;
p[i]=x;
}
}

}
}
}
"``````
3
Contributors
3
Replies
4
Views
7 Years
Discussion Span
Last Post by cooldev

I got how you are trying to generate the prime numbers but you have messed it up to a great extent.

>Assume another variable lim which has the maximum index of prime numbers stored in array p.That is if you have got 3 prime numbers p[1],p[2],p[3] then lim is 3 and a variable called flag which signifies divisible if 1 and not divisible if 0.
>Just after your

if (num<5)
for(j=1;j<=((num+1)/2);j++)
printf("%d,",p[j]);
else
{
for(j=1;j<=3;j++)
printf("%d,",p[j]);

step do this :

``````x=6;
while(x<num)
{
flag=0;//Signifies not divisible
for(i=1;i<=lim;i++)
{
if(x%p[i]==0)
{
flag=1; //shows its divisible
break;
}
}
if(flag==0)
{
p[++lim]=x;
}
x++;
}
//Print the array p[] from 1 to lim here and you are done.``````

Its just this much even if I follow your algorithm.You are just confused.Take time to view your code once and the optimized code given above.And ya put your codes within code tags from next time.

I got it to work- i modified line 76 to

``if((prime) && (x<=num))``

works fine now,

Enter the number:40
The primes are :2,3,5,7,11,13,17,19,23,29,31,37,Press any key to continue . . .