Sunday, 10 March 2013

Prime Factorisation - programming

Thought I'd test my programming skills by making a program which tells you the prime factorisation of a number or range of numbers. i.e:

4 = 2 x 2
10 = 2 x 5
20 = 2 x 2 x 5

etc...

Here's the code which works it out for a series of numbers:

//
//  main.c
//  printInPrimeFactors
//
//  Created by Monkey on 10/03/2013.
//  Copyright (c) 2013 Monkey. All rights reserved.
//

#include

#define TRUE 1
#define FALSE 0

int isPrime (int number);
int printInPrimeFactors (int number);

int main(int argc, const char * argv[])
{
    //scan in a number
    int startNumber = 0;
    printf("Type a starting number: ");
    scanf("%d", &startNumber);
    
    int endNumber = 0;
    printf("Type an end number: ");
    scanf("%d", &endNumber);
    
    //find the prime factors of range of numbers
    for (int i=startNumber; i<=endNumber; i++) {
        printInPrimeFactors(i);
    }
    
        return 0;
}

int printInPrimeFactors (int number) {
    //printf("finding the prime factors of %d.....\n", number);
    
    //if it's a prime just print it and return to main
    if (isPrime(number)) {
        printf("%d\n", number);
        return 0;
    }
    
    //for nice formatting I'm printing the number =
    printf("%d = ", number);
    
    //testing to find a factor of the number, which is also prime
    for (int i =2; i < number; i++) {
        if (number %i == 0 && isPrime(i)) {
            //printf("a prime factor of %d is %d\n", number, i);
            
            //testing to see how many times the number can be divided by 'i' and printing i each time
            //printf("testing to see how many times %d can divide by %d\n", number, i);
            int result = number;
            while (result % i == 0) {
                printf("%d x ", i);
                result = result / i;
            }
            
            //print an extra line to make it look nice
            //printf("\n");
        }
    }
    
    //print new line for next number
    printf("1\n");
    return 0;
}



//a function which returns true or false if number is prime
int isPrime (int number) {
    //printf("testing to see if %d is a prime\n", number);
    int prime = TRUE;
    
    //test to see if it is divisible by any other numbers
    for (int i = 2; i < number; i++) {
        if (number %i ==0) {
            prime = FALSE;
            //printf("%d is not a prime number\n", i);
            return prime;
        }
    }
    return prime;
}

output:
Type a starting number: 100
Type an end number: 120
100 = 2 x 2 x 5 x 5 x 1
101
102 = 2 x 3 x 17 x 1
103
104 = 2 x 2 x 2 x 13 x 1
105 = 3 x 5 x 7 x 1
106 = 2 x 53 x 1
107
108 = 2 x 2 x 3 x 3 x 3 x 1
109
110 = 2 x 5 x 11 x 1
111 = 3 x 37 x 1
112 = 2 x 2 x 2 x 2 x 7 x 1
113
114 = 2 x 3 x 19 x 1
115 = 5 x 23 x 1
116 = 2 x 2 x 29 x 1
117 = 3 x 3 x 13 x 1
118 = 2 x 59 x 1
119 = 7 x 17 x 1
120 = 2 x 2 x 2 x 3 x 5 x 1

after all that I found this nice website which basically does the same!

No comments:

Post a Comment