Prime number generator that works but needs improvement

[cooldev]

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;
                }
            }
	
        }
	}
}
"

[Pavan_]

For finding prime numbers upto a given no, Use "The Sieve of Eratosthenes algorithm"http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

that is a gud way to find out effectively

[csurfer]

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.

[cooldev]

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 . . .