From 0c7cf202fabe4cd1845963ae24955f7636ca5c7b Mon Sep 17 00:00:00 2001
From: kittobi1992 <kittobi1992@users.noreply.github.com>
Date: Sat, 22 Nov 2014 12:14:18 +0100
Subject: Create factor.cpp

Factorize a number n
---
 math/factor.cpp | 45 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 45 insertions(+)
 create mode 100644 math/factor.cpp

(limited to 'math')

diff --git a/math/factor.cpp b/math/factor.cpp
new file mode 100644
index 0000000..43aeae3
--- /dev/null
+++ b/math/factor.cpp
@@ -0,0 +1,45 @@
+#include <iostream>
+#include <vector>
+
+using namespace std;
+
+typedef unsigned long long ll;
+
+const ll PRIME_SIZE = 10000000;
+vector<int> primes;
+
+//Call before calculating anything
+void primeSieve() {
+	vector<int> isPrime(PRIME_SIZE,true);
+	for(ll i = 2; i < PRIME_SIZE; i+=2) {
+		if(isPrime[i]) {
+			primes.push_back(i);
+			if(i*i <= PRIME_SIZE) {
+				for(ll j = i; i*j < PRIME_SIZE; j+=2) isPrime[i*j] = false;
+			}
+		}
+		if(i == 2)
+			i--;
+	}
+} 
+
+//Factorize the number n
+vector<int> factorize(ll n) {
+	vector<int> factor;
+	ll num = n;
+	int pos = 0;
+	while(num != 1)  {
+		if(num % primes[pos] == 0) {
+			num /= primes[pos];
+			factor.push_back(primes[pos]);
+		}
+		else
+			pos++;
+		if(primes[pos]*primes[pos] > n)
+			break;
+	}
+	if(num != 1)
+		factor.push_back(num);
+	return factor;
+	
+}
-- 
cgit v1.2.3