Lars Yencken avatar Lars Yencken committed dc722a7

C++ 03.

Comments (0)

Files changed (2)

cpp/03-prime-factors.cpp

+/*
+ *
+ *  03-prime-factors.c
+ *  euler
+ *
+ *  Created by Lars Yencken on 2012-03-01.
+ *  Copyright 2012 Lars Yencken. All rights reserved.
+ *
+ */
+
+#include <iostream>
+#include <vector>
+#include <cmath>
+
+using namespace std;
+
+/**
+ * Find all the primes between 2 and n.
+ */
+void prime_sieve(uint64_t n, vector<uint64_t>& primes)
+{
+	primes.clear();
+
+	vector<bool> is_prime;
+	is_prime.reserve(n + 2);
+
+	// initialise to true
+	for (uint64_t i = 0; i <= n; i++)
+	{
+		is_prime.push_back(true);
+	}
+
+	for (uint64_t i = 2; i <= n; i++)
+	{
+		if (is_prime[i])
+		{
+			// mark all its multiples as not prime
+			for (uint64_t j = i + i; j <= n; j += i)
+			{
+				is_prime[j] = false;
+			}
+		}
+	}
+
+	// keep the primes we found
+	for (uint64_t i = 2; i <= n; i++)
+	{
+		if (is_prime[i])
+		{
+			primes.push_back(i);
+		}
+	}
+}
+
+/**
+ * Factorize n using the trial division method, storing each prime factor
+ * into the given factors vector.
+ */
+void trial_division(uint64_t n, vector<uint64_t>& factors)
+{
+	factors.clear();
+
+	vector<uint64_t> primes;
+	prime_sieve((uint64_t)pow(n, 0.5) + 1, primes);
+	uint64_t p;
+	for (vector<uint64_t>::iterator it = primes.begin(); it != primes.end();
+			it++)
+	{
+		p = *it;
+		if (p * p > n)
+		{
+			break;
+		}
+		while (n % p == 0)
+		{
+			factors.push_back(p);
+			n /= p;
+		}
+	}
+
+	if (n > 1)
+	{
+		factors.push_back(n);
+	}
+}
+
+int main(int argc, const char *argv[])
+{
+	const uint64_t n = 600851475143;
+	vector<uint64_t> factors;
+	trial_division(n, factors);
+	cout << factors[factors.size() - 1] << endl;
+	return 0;
+}
 CXX = clang++
 
 ALL = 01-sum-numbers \
-	  02-sum-fibonacci
+	  02-sum-fibonacci \
+	  03-prime-factors
 
 all: $(ALL)
 
 02-sum-fibonacci: 02-sum-fibonacci.cpp
 	$(CXX) -o $@ $<
 
+03-prime-factors: 03-prime-factors.cpp
+	$(CXX) -o $@ $<
+
 clean:
 	rm -f $(ALL)
 
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.