1

I have written some code to solve the british informatics olympiad question 1 (2012) in c. If it is of any help to anyone, or possibly of interest, the program finds the product of the unique prime factors of a number. If the number is prime, it returns the original number.

It is supposed to work up to an input of 1 000 000 and it does so when compiled on linux and mac.

For some reason when it is compiled on windows (using the mingw compiler) it does not work for an input above 520558!

It is probably something to do with the declaration of an array that is 520558 integers long but I have no idea how to remedy it.

Any help would be much appreciated

Thanks.

Code:

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

int main(int argc, char* argv[]){
    printf("Please enter your input: ");
    int input;
    scanf("%d",&input);
    int numbers[input-2];
    for (int i=0;i<input-2;i++) {
        numbers[i] = i+2;
    }
    for (int i=0;i<input-2;i++) {
        if(numbers[i] == 0) {
            continue;
        }else{
            for (int j=(i+2)*2;j<input;j+=numbers[i]){
                numbers[j-2] = 0;
            }
        }
    }
    int product = 1;
    for (int i=0;i<input-2;i++) {
        if(numbers[i]!=0){
            if(input%numbers[i]==0) {
                product *= numbers[i];
            }
        }
    }
    if(product == 1){
        printf("%u",input); 
    }else{
        printf("%u",product);
    }
    printf("\n");
    // Get rid of this on mac and linuxs
    system("PAUSE");
    return 0;
}
4

3 回答 3

3

int numbers[input-2];

这会在堆栈上创建一个整数数组。堆栈的大小是有限的;这通常是几兆字节或更少的 2 的幂。520558 可疑地接近 2^19,表明堆栈区域为 2Mb。

如果你正在处理这么大的数组,你应该使用堆来代替:

int * numbers = (int*)malloc((input-2)*sizeof(int)); 
. 
. 
. 
free(numbers); 
return 0;
于 2012-08-21T16:19:40.027 回答
2

尝试用numbers这个替换你的声明:

int* numbers = (int *) malloc((input-2)*sizeof(int));

正如 squiguy 所提到的,这将在堆上动态分配数组,避免您可能遇到的任何潜在堆栈问题。您还应该在完成后释放它,使用:

free(numbers);
于 2012-08-21T16:24:06.677 回答
0

最好numbers在堆而不是堆栈上分配变量:

#define MAXNUMS 1000000
int numbers[MAXNUMS];

int main() {
...
}
于 2012-08-21T16:19:16.097 回答