Mai 2016 – mborm.net

Hier meine Brute Force Lösung zu Problem 50.

Befehl zum Compilieren und Ausführen sowie die Ausgabe mit Zeitmessung:

gcc -O3 -march=native -mtune=native -std=c11 -ffast-math -fopenmp Prob50.c -lm -o Prob50 && time ./Prob50 Result: 997651 with 543 terms

real 0m2.809s user 0m16.577s sys 0m0.012s

Und der Code:

#include <stdio.h>

#define ARRLENGTH(x) (sizeof(x) / sizeof((x)[0]))

static unsigned int prmlst[78498];

inline static unsigned int isPrime(unsigned int n) {
    if(n == 1)
        return 0;

    else if(n == 2)
        return 1;

    else {
        int i, r = (int) __builtin_sqrt(n);

        for(i = 2; i <= r && n % i != 0; ++i);

        return (r == i - 1) ? 1 : 0;
    }
}

inline static unsigned int getConPrmCnt(unsigned int n) {
    unsigned int sum = 2, prm = 1, cnt = 1, sumcnt = 0;

    while(sum != n) {
        sum = prmlst[sumcnt++];
        prm = 1;
        cnt = sumcnt;

        while(sum < n) {
            sum += prmlst[cnt++];
            prm++;
        }
    }

    return (sum == n) ? prm : 0;
}

int main(void) {
    unsigned int idx = 0, res = 0;

    for(unsigned int i = 0; i < 1000000; i++)
        if(isPrime(i))
            prmlst[idx++] = i;

    #pragma omp parallel for
    for(unsigned int i = 0; i < ARRLENGTH(prmlst); i++) {
        unsigned int tmp = getConPrmCnt(prmlst[i]);

        if(tmp > res) {
            res = tmp;
            idx = prmlst[i];
        }
    }

    printf("Result: %u with %u terms\n", idx, res);
}

#include <stdio.h>

#define ARRLENGTH(x) (sizeof(x) / sizeof((x)[0]))

static unsigned int prmlst[78498];

inline static unsigned int isPrime(unsigned int n) {

if(n == 1)

return 0;

else if(n == 2)

return 1;

else {

int i, r = (int) __builtin_sqrt(n);

for(i = 2; i <= r && n % i != 0; ++i);

return (r == i - 1) ? 1 : 0;

}

inline static unsigned int getConPrmCnt(unsigned int n) {

unsigned int sum = 2, prm = 1, cnt = 1, sumcnt = 0;

while(sum != n) {

sum = prmlst[sumcnt++];

prm = 1;

cnt = sumcnt;

while(sum < n) {

sum += prmlst[cnt++];

prm++;

}

return (sum == n) ? prm : 0;

}

int main(void) {

unsigned int idx = 0, res = 0;

for(unsigned int i = 0; i < 1000000; i++)

if(isPrime(i))

prmlst[idx++] = i;

#pragma omp parallel for

for(unsigned int i = 0; i < ARRLENGTH(prmlst); i++) {

unsigned int tmp = getConPrmCnt(prmlst[i]);

if(tmp > res) {

res = tmp;

idx = prmlst[i];

}

printf("Result: %u with %u terms\n", idx, res);

}

Hier meine Lösung zu Problem 35. Für alle Primzahlen unter 1 Mio werden die jeweiligen Permutationen untersucht. Sind diese auch alles Primzahlen handelt es sich um eine kreisförmige Primzahl (Circular Prime Number).

Output mit Geschwindigkeit:

Result: 55

real 0m0.598s user 0m0.717s sys 0m0.020s

und dazu der Java-Code:

public final class Prob35 {

    private final static boolean isPrime(int n) {
        if(n == 1)
            return false;
 
        if(n == 2)
            return true;
 
        int r = (int) Math.floor(Math.sqrt(n));
        int i;

        for(i = 2; i <= r && n % i != 0; ++i) {}
 
        return (r == i - 1);
    }

    private final static boolean isCircular(int n) {
        String s = Integer.toString(n);

        for (int i = 0; i < s.length(); i++)
            if(!isPrime((Integer.parseInt(s.substring(i) + s.substring(0, i)))))
                return false;

        return true;
    }

    public static void main(String[] argv) {
        int cnt = 0; 

        for(int i = 0; i < 1_000_000; i++)
            if(isPrime(i))
                if(isCircular(i))
                    ++cnt;

        System.out.println("Result: "+cnt);
    }
}

public final class Prob35 {

private final static boolean isPrime(int n) {

if(n == 1)

return false;

if(n == 2)

return true;

int r = (int) Math.floor(Math.sqrt(n));

int i;

for(i = 2; i <= r && n % i != 0; ++i) {}

return (r == i - 1);

}

private final static boolean isCircular(int n) {

String s = Integer.toString(n);

for (int i = 0; i < s.length(); i++)

if(!isPrime((Integer.parseInt(s.substring(i) + s.substring(0, i)))))

return false;

return true;

}

public static void main(String[] argv) {

int cnt = 0;

for(int i = 0; i < 1_000_000; i++)

if(isPrime(i))

if(isCircular(i))

++cnt;

System.out.println("Result: "+cnt);

}

mborm.net

Ein Computerprogramm tut was Du schreibst, nicht was Du willst.

Monat: Mai 2016

Problem 50 auf projecteuler.net

Problem 35 auf projecteuler.net