## 11064 - Number Theory

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
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
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)
Darko wrote:
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
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia
leocm wrote:
Darko wrote: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
New poster
Posts: 22
Joined: Fri Jul 21, 2006 9:44 am
Location: Brasil
Thank you by the answers!

ayeshapakhi
Learning poster
Posts: 60
Joined: Sun Apr 16, 2006 7:59 pm

### al last got AC

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
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:
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 ) ...``

Code: Select all

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

leeyeanhoo
New poster
Posts: 4
Joined: Sat Nov 04, 2006 5:40 am

### wow..

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

rossi kamal
New poster
Posts: 14
Joined: Mon Sep 03, 2007 10:11 am
Contact:

### 11064

is it that we are to find cototients?

New poster
Posts: 32
Joined: Tue Feb 13, 2007 1:31 pm

### Re: 11064 - Number Theory

sample input

Code: Select all

``````1234567890
987654321
40
700
17
43
``````
sample output

Code: Select all

``````905527555
367951264
17
443
0
0
``````

xtremedreamer
New poster
Posts: 5
Joined: Sun Dec 21, 2008 7:19 am

### Re: 11064 - Number Theory

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
New poster
Posts: 15
Joined: Thu Jul 08, 2010 8:28 am

### Re: 11064 - Number Theory

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