> The prime factors of 13195 are 5, 7, 13 and 29.
>What is the largest prime factor of the number 600851475143 ?
Can anyone help me on this one? I'm learning C# and having a hard time grasping the logic here. I'm supposed to calculate prime numbers first right? But I just can't find a good formula for that
This isn't homework or anything, just something I'm taking up in my spare time.
Watch Numberphile on YouTube for this kind of problems solved fun way. James Grime is my hero.
make an array on n numbers from 2 to the numer you want - 1,then if a number divides n then every a*k in the array is turned into a zero, then go to the next non-zero number and repeat the process, if you want instead of the array being from 1 to n make it from 1 to sqrt(n)
after the process the array has the factors of the number.
>implying Sup Forums doesn't know about project Euler
naive algorithm for prime factorization would be (sorry don't know C#)
def factorize(num):
primes = list()
while num != 1:
for i in range(2, int(num+1)):
if num % i == 0:
primes.append(i)
num /= i
break
return primes
print(factorize(600851475143))
>[71, 839, 1471, 6857]
what? I put a picture of the man on the thread...
Nice one, thanks. I'll try to convert this to code tomorrow
Looks good, I understand everything but 'num /= 1' (divide equals??)
that's 'i', not 1. The /= is division, similar to += for addition.
nun /= i is same as num = num / i
$ /usr/bin/factor 600851475143
600851475143: 71 839 1471 6857
Part of the GNU coreutils
Here is the code btw
void factors(long n) {
int j;
long sieve = sqrt(n) +1;
int c = 0;
int *arr = new int[sieve];
for (int i = 0; i < sieve; i++) arr[i] = i + 2;
for (int i = 0; i < sieve; i++) {
if (arr[i] != 0) {
if (n % arr[i] == 0) {
c++;
j = arr[i]+i;
while (j < sieve) {
arr[j] = 0;
j+=arr[i];
}
} else arr[i] = 0;
}
}
for (int i = 0; i < sieve; i++) {
if (arr[i] != 0) {
cout
Neat
>just make an array with 600 billion elements
Use a sieve and run it for a week :^)
>he can't make an array of 77459 elements
Man your solution runs way quicker, I had a bad approach doing something akin to fin the prime numbers.
you don't need to verify until n. Remember there are no prime factors higher than sqrt(n).
>the modulo operator
its that simple.
Fundamental theorem of arithmetic is your friend.
I'll take a look, thanks.
What if n is prime?
Project Euler thread?
Pic related is me, I've been doing them on and off since the begining of summer or so.
I like using the earlier problems as an introduction to new languages, it's like the mathematical equivalent of Hello world.
You can do from 2 to N/2 - 1, because there will be no prime factors from N/2 to N. Depending on the other factors involved, you could dynamically shrink the upper bound of the factor check.
Some sieve of Erathostenes -even an imperfect one- will do.