From 7b7c97be0cba9282c01d6661e0eff394e7c0ebbb Mon Sep 17 00:00:00 2001
From: Paulo Custodio <pauloscustodio@gmail.com>
Date: Wed, 23 Jun 2021 21:51:59 +0100
Subject: Add C and C++ solutions to challenge 008

---
 challenge-008/paulo-custodio/cpp/ch-1.cpp | 67 +++++++++++++++++++++++++++++++
 1 file changed, 67 insertions(+)
 create mode 100644 challenge-008/paulo-custodio/cpp/ch-1.cpp

(limited to 'challenge-008/paulo-custodio/cpp/ch-1.cpp')

diff --git a/challenge-008/paulo-custodio/cpp/ch-1.cpp b/challenge-008/paulo-custodio/cpp/ch-1.cpp
new file mode 100644
index 0000000000..9915f46bb8
--- /dev/null
+++ b/challenge-008/paulo-custodio/cpp/ch-1.cpp
@@ -0,0 +1,67 @@
+/*
+Challenge 008
+
+Challenge #1
+Write a script that computes the first five perfect numbers. A perfect number
+is an integer that is the sum of its positive proper divisors (all divisors
+except itself). Please check Wiki for more information. This challenge was
+proposed by Laurent Rosenfeld.
+*/
+
+#include <iostream>
+using namespace std;
+
+bool is_prime(int n) {
+    if (n <= 1)
+        return false;
+    if (n <= 3)
+        return true;
+    if ((n % 2) == 0 || (n % 3) == 0)
+        return false;
+    for (int i = 5; i * i <= n; i += 6)
+        if ((n % i) == 0 || (n % (i + 2)) == 0)
+            return false;
+    return true;
+}
+
+int next_prime(int n) {
+    if (n <= 1)
+        return 2;
+    do {
+        n++;
+    } while (!is_prime(n));
+    return n;
+}
+
+int ipow(int base, int exp) {
+    int result = 1;
+    for (;;) {
+        if (exp & 1)
+            result *= base;
+        exp >>= 1;
+        if (!exp)
+            break;
+        base *= base;
+    }
+    return result;
+}
+
+// Euclid proved that 2 ^ (p-1) * (2 ^ p - 1) is an even perfect number
+// whenever 2^p - 1 is prime
+int next_perfect(void) {
+    static int p = 1;
+    while (true) {
+        p = next_prime(p);
+        int f = ipow(2, p) - 1;
+        if (is_prime(f))
+            return ipow(2, p - 1) * f;
+    }
+}
+
+int main(int argc, char* argv[]) {
+    int n = 5;
+    if (argc == 2)
+        n = atoi(argv[1]);
+    for (int i = 0; i < n; i++)
+        cout << next_perfect() << endl;
+}
-- 
cgit