Member Avatar for 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;
                }
            }
	
        }
	}
}
"

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.

Member Avatar for 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 . . .

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.