Thread: Show prime #'s and factors of non-primes

I need help. I am trying to write a program that will allow the user to enter any number. The program will then display the factors of that number i.e. 24=2x2x2x3 . If the number is prime like 17, the program will just print to screen "number is prime. I'm a rank novice at this. What is the best loop to use for this program? I would greatly appreciate as much detail as you can afford to give. Thanks.

Signed,

Grey matter flatulence

You know, just the other day I was talking to a classmate about how important number theory is to compuer science...

The simplest formula for factoring a number is probably this..

Code:

for (i = 2; i <= n; i++)
{
 while (n is divisible by i)
 {
  printf ("%d is a factor.", i);
  n /= i;
 }
}

It isn't complete.. but it's enough that you should be able to execute it by hand for small numbers and get the feel of the algorithm.

If I might make a suggestion, try making a program to generate prime numbers, like you run it and the output would be like...

Code:

C:\>prime.exe
2
3
5
7
11
13
17

Once you make a program that can do that, you've already made a program that checks to see if a number is prime, and more than likely the method for doing so will easily translate to factoring a number.

Search for factors and if you find it keep dividing by it till the number is no longer divisble by it, after you are done with 2 you can start with 3 increment by 2 as all the other factors will be odd also note 0 and 1 are neither composite nor prime ,
the program below is slightly longer then a program which would just print factors as I didnt want to print the factors if the number happened to be prime .

#include <stdio.h>

/*works only for non negative integers */
void factorize(int i)
{
int j=2,temp=i,count=0;
if(i<=1) {
printf("neither prime nor composite");
return;
}
for(count=0; (i>1) && ((i&1)==0);count++) i>>=1;
if( (i==1) && (count==1) ) {
printf("prime");
return;
}
else while(count--) printf(" 2 ");
for(j=3;i>1;j+=2) {
for(count=0; (i%j)==0;count++) i /= j;
if(j==temp) {
printf("prime");
return;
}
else while(count--) printf(" %d ",j);
}
}

int main(void)
{
int i;
printf("Give a non negative number:");
scanf("%d",&i);
factorize(i) ;
return 0;
}