UIU: Competitive Programming: Prime Factor


Prime factor


// @BEGIN_OF_SOURCE_CODE
 
#include <cstdio>
#import <cmath>
 
using namespace std;
 
bool isPrime(int n)
{
    if ( n < 2 ) return false;
 
    if ( n == 2 ) return true;
 
    if ( n % 2 == 0 ) return false;
 
    int squareRoot = (int) sqrt(n);
 
    for ( int i = 3; i <= squareRoot; i += 2 ) {
        if ( n % i == 0 ) return false;
    }
 
    return true;
}
 
int nextPrime(int n)
{
    while(!isPrime(++n));
 
    return n;
}
 
int main(int argc, const char * argv[])
{
    // 36 = 2 * 2 * 3 * 3;
    int input;
 
    scanf ("%d", &input);
 
    int primeNumber = nextPrime(0);
 
    while (input != 1) {
        while (input % primeNumber == 0) {
            printf ("%d\n", primeNumber);
            input /= primeNumber;
        }
 
        primeNumber = nextPrime(primeNumber);
    }
 
    return 0;
}
 
// @END_OF_SOURCE_CODE

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s