UNIX for Dummies Questions & Answers

I am using ubuntu. I have written a program to calculate prime factors. it works perfectly fine till entered number is less than 9989 (or so ) but when one enters a number higher than that, for example 15000, it does not work. Can anyone guide me whats the problem ? although new codes are welcome, but i want to know problem with my code. thanks in Advance

Code:

 #include<stdio.h>
void prime_factors( int );
int next_prime_no( int );
int main()
{
	int num;
	printf("Enter a number : ");
	scanf("%d",&num);
	prime_factors(num);
	return 0;
}
void prime_factors( int a)
{
	int r,p,c=a;
	for(p=2;p<=c;p=next_prime_no(p))		//checking for prime factors starting from 2 and then finding next higher prime number
	{
		while(a>0)		
		{
			if(p==c)			//printing the number itself if no prime factors other than itself.
			{
				printf(" Factors of %d are 1 and %d \n\n",c,c);
				a=0;
				break;
			}
			else
			{	
				r=a%p;
				if(r==0)
				{
					printf(" %d ",p);
					a=a/p;
				}
				else
				{
				break;
				}
			}
		}
	}
	printf("\n\n\n");	
}
int next_prime_no(int p)				// finding the next higher prime number
{
	int i,r,j;
	for(i=p+1;i<10000;i++)
	{
		r=0;
		for(j=2;j<i;j++)
		{
			r=i%j;
			if(r==0)
			break;
		}
		if(r!=0)
		{
			return i;
			break;
		}
	}
}

Fair enough. The first problem, without even looking at what your code does, is obvious: use speaking names for your variables. Instead of juggling around "i", "j", "k", "p" and whatnot, like in good old FORTRAN/77, you should write names which tell you instantly what is in them: numbers, primes, factors, whatever. Not only will that help you with housekeeping, it will help you to concentrate on coding instead of remembering what "i" exactly means now in this function.

My personal favorite in this regard (but that is a matter of taste) is "Hungarian Style Notation" - or at least some personal subset variation of it. I prefix my variables names with a type indicator, which helps remembering this vital fact.

Secondly, regarding your code: the problem you are experiencing is IMHO in the function next_prime(), in this line:

Code:

	for(i=p+1;i<10000;i++)

Actually the program does what you told it to do and therefore this loop is interrupted at 9999 (not "9989 (or so )", as you said).

Aside from that your code inefficient to the extreme. Because "2" is a prime you could skip all even numbers and increment i by 2 instead of one, yes? This, btw., could be done with all the other found primes too. This consideration is the basis of the "Sieve of Eratosthenes", which will work for very small numbers like the ones you deal with. For bigger numbers you need better algorithms, like Lucas-Lehmer, Adleman-Pomerance-Rumely, etc..

For a quick introduction to primality tests and their pros and cons start with searching for "Primality Test" in Wikipedia.

I hope this helps.

bakunin

Thanks a lot!!! I am gonna keep in mind what you just told me about using variables! your reply really helped a lot! Thanks again.