Show prime #'s and factors of non-primes

This is a discussion on Show prime #'s and factors of non-primes within the C Programming forums, part of the General Programming Boards category; I need help. I am trying to write a program that will allow the user to enter any number. The ...

  1. #1
    Unregistered
    Guest

    Question 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

  2. #2
    Registered User
    Join Date
    Sep 2001
    Posts
    752
    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.

  3. #3
    Registered User pinko_liberal's Avatar
    Join Date
    Oct 2001
    Posts
    284
    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;
    }

Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21