цикл for неожиданно падает в значении - PullRequest
Новая
       10

цикл for неожиданно падает в значении

0 голосов
/ 27 марта 2019

Предположение Гольдбаха гласит, что каждое четное число, превышающее 4, является суммой двух простых чисел. Я пишу программу на C для поиска этих пар. Для этого он сначала находит все простые числа, меньшие заданного пользователем числа. У меня есть цикл for для итерации от 4 до заданного пользователем числа и поиска пар в теле цикла. Когда этот цикл достигает примерно 40, он внезапно перепрыгивает назад примерно на 30, а затем продолжает итерацию вверх (с пользовательским вводом 50 он перепрыгнул с 38 до 9, с вводом 60 - с 42 до 7). Я не могу понять, почему это происходит. Вот мой код: 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/types.h>
#include <unistd.h>

struct pair{
    int a;
    int b;
}pair_t;


int main(){
    int N;
    int numPrimes = 1;
    int *primes = malloc(100*sizeof(int));
    int isPrime = 1;
    primes[0] = 2;
    int timesRealloc = 0;
    int availableSlots = 100;

    printf("Please enter the largest even number you want to find the Goldbach pair for: \n");
    scanf("%d", &N);

    struct pair pairs[N/2 + 4];

    int j = 0;
    int i;
    for (i = 3; i <= N; i+=2){ 
        j = 0;
        isPrime = 1;
        while (primes[j] <= sqrt(i)) {
            if (i%primes[j] == 0) {
                isPrime = 0;
                break;
            }
            j++;
        }
        if (isPrime == 1){
            primes[numPrimes] = i;
            numPrimes++;
        }
        if (availableSlots == numPrimes){
            timesRealloc++;
            availableSlots += 100;
            primes = realloc(primes, availableSlots*sizeof(int));
        }
    }

    printf("The largest prime I found was %d\n", primes[(numPrimes-1)]);

    int k;
    for (i=4; i<=N; i+=2){
        printf("i is %d, N is %d\n", i, N);
        if (i > N){ break; }
        for (j=0; j<numPrimes; j++){
            for (k=0; k<numPrimes; k++){
                int sum = primes[j] + primes[k];
                if(sum == i){
                    pairs[i].a = primes[j];
                    pairs[i].b = primes[k];
                }
            }
        }
    }

    for (i=4; i<=N; i+=2){
        printf("%d is the sum of %d and %d\n", i, pairs[i].a, pairs[i].b);
    }

    return 0;
}

1 Ответ

0 голосов
/ 27 марта 2019

Вы пытаетесь экономить место, сжимая массив pairs, чтобы просто удерживать все остальные (четные) числа и начинать с 4 вместо нуля. Однако вы просчитываете его размер, а затем, когда начинаете использовать его, вы обращаетесь с ним, как будто он не сжат, и что для каждого натурального числа есть слот.

Код страдает от вычисления основного массива в main() вместе с другим кодом, это лучше всего отделить. И когда он ищет пары, он не завершает работу, когда находит их, и когда он начинает получать суммы, превышающие целевую. Моя доработка ниже пытается решить все эти проблемы: 

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <stdbool.h>

#define INITIAL_SLOTS (100)

struct pair {
    int a;
    int b;
} pair_t;

int compute_primes(int limit, unsigned **primes, int size) {
    int numPrimes = 0;

    (*primes)[numPrimes++] = 2;

    for (int i = 3; i <= limit; i += 2) { 
        bool isPrime = true;

        for (int j = 0; (*primes)[j] <= i / (*primes)[j]; j++) {
            if (i % (*primes)[j] == 0) {
                isPrime = false;
                break;
            }
        }

        if (isPrime) {
            (*primes)[numPrimes++] = i;
        }

        if (numPrimes == size) {
            size *= 2;
            *primes = realloc(*primes, size * sizeof(unsigned));
        }
    }

    return numPrimes;
}

int main() {
    int N;
    printf("Please enter the largest even number you want to find the Goldbach pair for: \n");
    scanf("%d", &N);

    unsigned *primes = calloc(INITIAL_SLOTS, sizeof(unsigned));
    int numPrimes = compute_primes(N, &primes, INITIAL_SLOTS);

    printf("The largest prime I found was %d\n", primes[numPrimes - 1]);

    struct pair pairs[(N - 4) / 2 + 1]; // compressed data structure

    for (int i = 4; i <= N; i += 2) {

        int offset = (i - 4) / 2; // compressed index
        bool found = false;

        for (int j = 0; ! found && j < numPrimes; j++) {
            for (int k = 0; ! found && k < numPrimes; k++) {
                int sum = primes[j] + primes[k];

                if (sum == i) {
                    pairs[offset].a = primes[j];
                    pairs[offset].b = primes[k];
                    found = true;
                } else if (sum > i) {
                    break;
                }
            }
        }
    }

    for (int i = 4; i <= N; i += 2) {
        int offset = (i - 4) / 2; // compressed index
        printf("%d is the sum of %d and %d\n", i, pairs[offset].a, pairs[offset].b);
    }

    free(primes);

    return 0;
}

OUTPUT 

> ./a.out
Please enter the largest even number you want to find the Goldbach pair for: 
10000
The largest prime I found was 9973
4 is the sum of 2 and 2
6 is the sum of 3 and 3
8 is the sum of 3 and 5
10 is the sum of 3 and 7
12 is the sum of 5 and 7
14 is the sum of 3 and 11
...
9990 is the sum of 17 and 9973
9992 is the sum of 19 and 9973
9994 is the sum of 53 and 9941
9996 is the sum of 23 and 9973
9998 is the sum of 31 and 9967
10000 is the sum of 59 and 9941
>
...