12 replies to this topic

[ghostrider_]

hello.. i want your help..
what i want to do is find the prime factors of a number.. specifically i want to check its largest prime factor, so as to see if the number is B-smmoth.. can anyone help me with a faster algorithm than trial division??

i have found those algorithms but i don't get them.. and i dont know if they are aproppriate..
any help??

http://en.wikipedia....Quadratic_sieve

http://en.wikipedia....ber_field_sieve

thanks..

[WingedPanther]

Both of these approaches are dealing with fairly advanced number theory. Unless you've had a course in the topic, it's not surprising if it doesn't make much sense. What size numbers are you planning to test?

[ghostrider_]

well, my project is going to be tested and it must check alla the numbers between 1 and 1000000, 1 and 1000000000..and find if they are B-smth (B a given mumber).. so i must factorize each one of the numbers between 1 and 1000000 ta least..

no faster idea than trial division?

[WingedPanther]

OK, given that I would stick with a much simpler factorization method, like build an array of prime factors and then cycle through it. Given the small size of the numbers you're dealing with, this should be adequate.

[ghostrider_]

WingedPanther said:

OK, given that I would stick with a much simpler factorization method, like build an array of prime factors and then cycle through it. Given the small size of the numbers you're dealing with, this should be adequate.

yep this is what i 've done... i am trying to find out if there is a way of "making" it a little bit faster than that..

what i ve done is construct a linked list of all the prime numbers and then check it's one number between 1 and 100.000.000 to find if its largest prime factor..

but i would appreciate if there are any ideas of making it faster than that.. thanks..

[WingedPanther]

One option would be to increment through the linked list, also dividing the target by found prime factors so that your search target is steadily shrinking as well.

[ghostrider_]

ok final ideas..
so to conclude.. i am about to build a list of primes up to 1024.. then i 've got two ideas.. the one -brute force divisibility testings..start from the firsti prime-divide until remainder <>0, then next prime etc..

but the other one- which if it is true may be fastest is: start from the nearest prime number to sqrt(n), see if it divides the number.. if not go to the previous one.. the firs to find is the largest.. do you think its ok??
my problem in the second idea is what will happen if the sqrt(n) is bigger than 1024.. how can i check if there is at least one prime factor between 1024 and sqrt(n)..??

[WingedPanther]

Consider this:
34 has two primes: 2 and 17. If you start at 6, and go down, you are moving away from the largest prime.

[ghostrider_]

so you say, build a linked list, and start dividing with the primes.. when remainder is <> 1 proceed to the next prime of the list... right?
any ideas for fastest algorithm?? because this one is a little bit slow...
let me ask you sth else.. i want the largest prime factor only to compare it with 1024.. and find all the numbers with largest prime factor less than 1024.. does this change anything??

[WingedPanther]

Consider a value like 2^30. How are you going to figure out the largest factor is 2?

[ghostrider_]

WingedPanther said:

Consider a value like 2^30. How are you going to figure out the largest factor is 2?

it works for that.. divide by the first prime number which is 2.. if the remainider is 0 then number =number /2.. then divide again by 2.. and again until the remainder is <>0... then do the same for next prime number-->3 and so on...
but its not a fast way..

[ghostrider_]

WingedPanther said:

Consider a value like 2^30. How are you going to figure out the largest factor is 2?

it works for that.. divide by the first prime number which is 2.. if the remainider is 0 then number =number /2.. then divide again by 2.. and again until the remainder is <>0... then do the same for next prime number-->3 and so on...
but its not a fast way..