Created
December 26, 2012 21:13
-
-
Save anonymous/4383220 to your computer and use it in GitHub Desktop.
Project Euler problem #3, not working for very large numbers.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <stdio.h> | |
#include <stdbool.h> | |
int main() | |
{ | |
//populate sieve array | |
int num=600851475143; | |
int num_array[num-1]; | |
int i, j; | |
int factor_mod; | |
int highest_prime=0; | |
for(i=1; i<num; i++) | |
{ | |
num_array[i] = i+1; | |
} | |
//get sieve array size | |
int div_array[0]; | |
int array_size = sizeof(num_array)/sizeof(div_array[0]); //why does this work? need to learn about sizeof | |
printf ("Sieve array size = %d\n", array_size); | |
//print starting sieve array | |
// printf("\nStarting sieve array: "); | |
// for(i=1; i<num; i++) | |
// { | |
// if(i<num) | |
// { | |
// printf("%d, ", num_array[i]); | |
// } | |
// else | |
// { | |
// printf("%d\n", num_array[i]); | |
// } | |
// } | |
//eliminate non-primes from num_array | |
for(i=2; i<num; i++)//need to find a better way to do this than nested for loops (?) | |
{ | |
for(j=2; j<num; j++) | |
{ | |
if(num_array[j]%i==0 && num_array[j]!=i) | |
{ | |
num_array[j] = 0; | |
} | |
} | |
} | |
//print modified sieve array | |
// printf("\nModified sieve array: "); | |
// for(i=1; i<num; i++) | |
// { | |
// if(i<num) | |
// { | |
// printf("%d, ", num_array[i]); | |
// } | |
// else | |
// { | |
// printf("%d\n", num_array[i]); | |
// } | |
// } | |
//divide number by non-zero entries in num_array to find highest prime factor | |
i = array_size; | |
while(highest_prime==0) | |
{ | |
if(num_array[i]!=0 && num%num_array[i]==0) //if number isn't 0 (is a prime), divide with modulus to determine if it is a factor | |
{ | |
highest_prime = num_array[i]; | |
} | |
i--; | |
} | |
//show result | |
printf("\nThe highest prime factor of %d is %d", num, highest_prime); | |
} | |
//Junk code | |
// for(i=array_size; i>2; i--) //start from highest numbers and decrement until you find the first non-zero entry | |
// { | |
// printf("\ni = %d, num_array[i] = %d", i, num_array[i]); | |
// if(num_array[i]!=0 && num%num_array[i]==0) //if number isn't 0 (is a prime), divide with modulus to determine if it is a factor | |
// { | |
// highest_prime = num_array[i]; | |
// printf("\nnum_array[i] = %d, num(mod)num_array[i] = %d, highest_prime = %d", num_array[i], num%num_array[i], highest_prime); | |
// } | |
// printf("\nhighest_prime post-if = %d", highest_prime); | |
// } | |
// printf("\nhighest_prime post-for = %d", highest_prime); |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment