Giuga-Zahlen berechnen

C :: Aufgabe #70 :: Lösung #3

4 Lösungen

#70

Anfänger - C von Gustl - 13.02.2015 um 12:42 Uhr

Eine natürliche Zahl n ist eine Giuga-Zahl, wenn alle ihre Primteiler p den Wert n/p - 1 teilen.

Schreibe ein Programm welches alle Giuga-Zahlen bis zu einer festen Obergrenze ausgibt.

Erläuterung zu einer Giuga-Zahl findest du hier: Wikipedia

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 eulerscheZhl (5230 Punkte) - 10.03.2015 um 16:41 Uhr

C-Code

#define LIMIT 1000000
#include <stdio.h>
 
void getSmallestFactor(int array[]) {
	int i, j;
    for (i = 2; i * i <= LIMIT; i++) {
        if (array [i] == 0) {
            for (j = 2 * i; j <= LIMIT; j += i) {
                if (array [j] == 0) {
                    array [j] = i;
                }
            }
        }
    }
}
 
int isGiuga(int n, const int primes[]) {
    int current = n;
    while (primes[current] != 0) {
        if ((n / primes [current] - 1) % primes [current] != 0)
            return 0;
        current /= primes [current];
    }
    return n != current && (n / current - 1) % current == 0;
}
 
int main() {
    int primes[LIMIT + 1] = {0};
    int i;
    getSmallestFactor (primes);
    for (i = 1; i <= LIMIT; i++) {
        if (isGiuga (i, primes)) {
            printf("%i\n", i);
        }
    }
    return 0;
}