From b5bac6bb92abbf57f1fe4fd425842aad3a435b5d Mon Sep 17 00:00:00 2001
From: kittobi92 <Tobias.Heuer@gmx.net>
Date: Tue, 12 Jan 2016 11:33:32 +0100
Subject: correct primeSieve and improve prime factorization

---
 math/factor.cpp | 39 ++++++++++++++++++++-------------------
 1 file changed, 20 insertions(+), 19 deletions(-)

(limited to 'math/factor.cpp')

diff --git a/math/factor.cpp b/math/factor.cpp
index 0cbca33..621d057 100644
--- a/math/factor.cpp
+++ b/math/factor.cpp
@@ -1,19 +1,20 @@
-const ll PRIME_SIZE = 10000000;
-vector<int> primes; //call primeSieve(PRIME_SIZE); before
-
-//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] > num) break;
-	}
-	if(num != 1) factor.push_back(num);
-	return factor;
-}
+typedef pair<int,int> ii;
+//Factorize a number n in its prime factors
+//Call primeSieve-method before with N > sqrt(n)
+//Return: Returns a vector of pairs, where the first entry in the pair is
+//the prime factor p and the second counts how many times p divides n
+vector<ii> factorize(ll n) {
+  vector<ii> fact; ll num = n, i = 0, c = 0;
+  while(num != 1) {
+    if(num % primes[i] == 0) {
+      c++; num /= primes[i];
+    } else {
+      if(c > 0)
+	      fact.push_back(make_pair(primes[i],c));
+      i++; c = 0;
+      if(primes[i]*primes[i] > num) break;
+    }
+  }
+  if(num != 1) fact.push_back(make_pair(num,c+1));
+  return fact;
+}
\ No newline at end of file
-- 
cgit v1.2.3