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
Location: Calgary, Canada

Post by Darko » Mon Aug 14, 2006 7:17 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.

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko » Mon Aug 14, 2006 10:50 am

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

Post by StatujaLeha » Mon Aug 14, 2006 11:21 am

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

Post by leocm » Mon Aug 14, 2006 8:52 pm

Thank you by the answers!

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

al last got AC

Post by ayeshapakhi » Tue Aug 15, 2006 8:30 am

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. :D

Zuza
New poster
Posts: 15
Joined: Tue Oct 05, 2004 8:31 pm
Location: Zagreb, Croatia
Contact:

Post by Zuza » Fri Sep 01, 2006 2:50 am

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
New poster
Posts: 4
Joined: Sat Nov 04, 2006 5:40 am

wow..

Post by leeyeanhoo » Mon Nov 06, 2006 4:14 am

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

Post by rossi kamal » Thu Sep 06, 2007 9:10 pm

is it that we are to find cototients?

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

Re: 11064 - Number Theory

Post by deadangelx » Sun Dec 28, 2008 5:25 pm

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

Post by xtremedreamer » Thu Jan 08, 2009 8:56 am

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

Post by anis_cuet016 » Wed Aug 25, 2010 12:26 am

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

Post Reply

Return to “Volume 110 (11000-11099)”