Symmetrische Primzahlen

2 Lösungen

#154

Anfänger - C von hollst - 03.04.2017 um 13:55 Uhr

Wieviele Primzahlen P < 1.000.000 sind rückwärts gelesen auch eine Primzahl, jedoch ungleich sich selbst?

Anmerkung: Die (Prim)zahlen 2, 3, 5, 7, 11 erfüllen nicht die Bedingungen (sind rückwärts gelesen sich selbst gleich),
als erste erfüllt die 13 die Bedingungen.

Bitte melden Sie sich an um zur Aufgabenbeschreibung eine Frage zu stellen.

Frage stellen

Bitte melden Sie sich an um eine Lösung einzureichen.

Lösung einreichen

von devnull (8870 Punkte) - 04.04.2017 um 15:36 Uhr

Konsolenausgabe:

13-31 17-71 37-73 79-97 107-701 113-311 149-941 157-751 167-761 179-971
199-991 337-733 347-743 359-953 389-983 709-907 739-937 769-967 1009-9001 
...
985799-997589 988199-991889 989099-990989 990799-997099 991499-994199 
991999-999199 995699-996599 
11184 Mirpzahlen unterhalb 1000000 gefunden.

C-Code

/*************************
 * mirp.c
 *************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define NOPRIME 0      // Marke Nicht-Primzahl
#define PRIME 1        // Marke Primzahl
#define EMIRP 2        // Marke symmetrische Primzahl (Mirpzahl)
#define MAX 1000000    // Array Limit

int numbers[MAX+1];
int max_num;

/* alle Vielfache von n auf NOPRIME setzen */
void set_mult_of_prime(int n) {
int m;
    m = n << 1;
    while(m <= max_num) {
        numbers[m] = NOPRIME;
        m += n;
    }
}

/* naechste Primzahl nach n (Marke PRIME) */
int get_next_prime(int n) {
    while(++n <= max_num && numbers[n] == NOPRIME)
        ;
    return n;
}

/* Ziffernfolge einer Zahl umkehren */
int rev_number(int n) {
    int rn=0;
    do {
        rn = rn*10 + n%10;
        n /= 10;
    } while(n!=0);
    return rn;
}

int main(int argc, char **argv) {
    int next_prime;
    int i, ri, cmirps;

    max_num = (argc==2) ? atoi(argv[1]) : MAX;
    if (max_num > MAX) max_num = MAX;

    /* alle Zahlen als PRIME markieren */
    for (i=0; i <= max_num; i++)
        numbers[i] = PRIME;
    numbers[1] = numbers[0] = NOPRIME;

    /* Primzahlensieb */
    next_prime = 2;
    do {
        set_mult_of_prime(next_prime);
        next_prime = get_next_prime(next_prime);
    } while (next_prime <= max_num);

    /* Primzahlen auf Symmetrie pruefen */
    cmirps = 0;
    for (i=0; i <= max_num; i++)
        if (numbers[i] == PRIME) {
			ri = rev_number(i);
			if (ri > i && numbers[ri] == PRIME) {
				numbers[i] = numbers[ri] = EMIRP;
				printf("%d-%d ", i, ri);
				cmirps+=2;
			}
		}
    printf("\n%d Mirpzahlen unterhalb %d gefunden.\n", cmirps, max_num);
    return 0;
}