mborm.net

Problem 50 auf projecteuler.netHier 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:
C
#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);
}

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

						#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);
}

					

			
 
Veröffentlicht am 21. Mai 2016 von admin in C, Programmierung, projecteuler
Problem 35 auf projecteuler.netHier 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:
Java
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);
    }
}

				
					
				1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

						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);
    }
}

					

			
 
Veröffentlicht am 19. Mai 2016 von admin in Java, Programmierung, projecteuler

		Neueste Beiträge
		
					apache2 TLS-Config für Qualys Lab Bestnote mit Server Hardening
									

					TEDP – The Energy Data Project
									

					GPU Benchmark integriert
									

					Neue Benchmark Version
									

					Eigene API für die luftdaten.info Wetterstation
									


		
KategorienAllgemein
Bash
C
Hardware
IT-Sicherheit
Java
Netzwerk
Perl
PHP
Programmierung
projecteuler
Python
Server
ArchivJanuar 2021
November 2020
Oktober 2019
September 2019
März 2019
Juli 2018
Juni 2018
August 2017
Mai 2016
Dezember 2015
Oktober 2015
August 2015
Juli 2015
Juni 2015
Mai 2015
April 2015
mborm.net

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

Problem 50 auf projecteuler.net

Problem 35 auf projecteuler.net

Neueste Beiträge

Kategorien

Archiv
