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