11064 - Number Theory

[Darko]

Do you have a list of the primes to do this? Until which number? If not, how can you "go through primes in order"?

Yes, first I build the list of primes, usually up to the square root of the maximum value. If the remaining number is not one after you went through the primes, that "remainder" is prime.

Now, how do I build the list of primes? I went through several different ways until I found out that (for me) sieve was the best way. Sometimes you can use just the sieve, or (like I did in this case), you do the sieve and then go through the sieve once and put all the primes into a list.

So, how do you do the sieve?
You know how it works? You start with 2 and mark all the multiples of 2. Then you find next unmarked (it will be 3) and mark all its multiples and so on. Note that you can start marking them from the square of the unmarked one (beacuse all smaller multiples were already marked). And you can stop looking for unmarked ones once you get to the square root of the sieve size. I will post the code I use if you want me to, but you might want to try building your own.

I hope this helped.

[Martin Macko]

Do you have a list of the primes to do this? Until which number? If not, how can you "go through primes in order"?

So, how do you do the sieve?
You know how it works? You start with 2 and mark all the multiples of 2. Then you find next unmarked (it will be 3) and mark all its multiples and so on. Note that you can start marking them from the square of the unmarked one (beacuse all smaller multiples were already marked). And you can stop looking for unmarked ones once you get to the square root of the sieve size. I will post the code I use if you want me to, but you might want to try building your own.

Leocm, here you can find a good article on the Prime Sieve of Eratosthenes.

[StatujaLeha]

How to do prime factorization efficiently? Well, I don't know, I just go through primes in order, nothing fancy, and it usually works fine.

Yes, I understand your point, but the question is:

Do you have a list of the primes to do this? Until which number? If not, how can you "go through primes in order"?

Thank you.

I have list of primes.
int KnownPrimes[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,
107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211};

First I go through this list. If number has factors not from this list then I find it by using simple bruteforce algorithm.

[leocm]

Thank you by the answers!

[ayeshapakhi]

hi Martin ......
infinite thanks for u....... atlast i got ac....
ur i/o helps me much......
the problem was in factorizing a number which is a product of only two primes.... i always make silly mistakes.....
thanks thanks...........and thanks.

[Zuza]

You might wanna watch out for this... ( I got TLE becouse of it )

i wrote

Code: Select all

for( int i = 2; i*i <= n; ++i ) ...

instead of

Code: Select all

for( long long i = 2; i*i <= n; ++i ) ...

enjoy...

[leeyeanhoo]

this people are very kind...! Im really appreciating the help

[rossi kamal]

is it that we are to find cototients?

[deadangelx]

sample input

Code: Select all

1234567890
987654321
40
700
17
43

sample output

Code: Select all

905527555
367951264
17
443
0
0

[xtremedreamer]

i can't understand how totient function helps here, because it only determines the number of relative primes for a number. Any body plz explain for input 10
totient(10) = 4
but for the problem the answer should be 3
how we can get it?

[anis_cuet016]

hey xtremedreamer !!!!!

check this out http://www.topcoder.com/tc?module=Stati ... imeNumbers ......
I guess u will find sth usefull. Or u may have already solved ....
Enjoy coding

Anis