wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> closest product of primes
        
(Message started by: pharaoh on Jan 17^th, 2007, 6:14am)

Title: closest product of primes
Post by pharaoh on Jan 17^th, 2007, 6:14am

A simple one..

Given any number Z, write a program to find two prime numbers whose product is closest to Z, and is not greater than or equal to Z.

That is, if Z is any positive integer, find P & Q such that:
Condition 1: P and Q are prime numbers both greater than 1 (P and Q may be equal)
Condition 2: Z - P*Q > 0 and (Z - P*Q) < (Z - X*Y) for all X & Y that satisfy Condition 1.

Example:
If Z is 12, then possible answers are 2x5 and 3x3.

The correct answer is (2,5) as 10 is closer to 12 than 9 (12-10 < 12-9).
1x11 is not considered as both X and Y should be greater than 1.

Title: Re: closest product of primes
Post by towr on Jan 17^th, 2007, 9:06am

What do we do for Z is 1,2,3 ?

And can we use a prime list of say all primes that are representable as integer?

I would suspect the search would be similar to the trivial way of seeking the largest square smaller than a given number. i.e. you iterate over the relevant numbers lower than http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/surd.gifZ

Title: Re: closest product of primes
Post by pharaoh on Jan 17^th, 2007, 9:36am

"What do we do for Z is 1,2,3 ?"

Forget them. ;D

"And can we use a prime list of say all primes that are representable as integer?"

I am not sure I understood this..What kind of list towr?
You can calculate the primes at run time right? No need to maintain any list.

Title: Re: closest product of primes
Post by towr on Jan 17^th, 2007, 9:39am

on 01/17/07 at 09:36:27, pharaoh wrote:

You can calculate the primes at run time right? No need to maintain any list.

That's rather horribly inefficient though, and I'd prefer to avoid it.
If you have a list, you can skip all number in between without first having to examine that they are in fact not primes.

Title: Re: closest product of primes
Post by Grimbal on Jan 17^th, 2007, 9:44am

And to test a number for primality it is good to have a list of smaller primes around.

Title: Re: closest product of primes
Post by pharaoh on Jan 17^th, 2007, 9:49am

towr, I agree that checking primality is costly but that is not something we are trying to formulate and optimize. The question demands a logic for finding two prime numbers whose product is closest to Z. So, even if you use the best primality algorithm or assume that you have a ready made list of primes the logic to find/pick up those 2 primes out of list will remain same.

I hope I am clear enough, infact the question is quite straight forward, thats why I called it simple to start with 8)

Title: Re: closest product of primes
Post by Grimbal on Jan 17^th, 2007, 10:03am

well, then

int bestp = 0;
int bestq = 0;
for( p=2 ; p<z ; p++ )
for( q=2 ; q<z ; q++ )
if( p*q<z && p*q > bestp*bestq ){
for( r=2 ; p%r ; r++ );
for( s=2 ; s%q ; s++ );
if( r==p && s==q ){
bestp = p;
bestq = q;
}
}

PS: I don't even know if it compiles.

Title: Re: closest product of primes
Post by pharaoh on Jan 17^th, 2007, 10:08am

Grimbal,
for( p=2 ; p<z ; p++ )
for( q=2 ; q<z ; q++ )

I think this is not needed, we can optimize this. What you say? Why check from 2 to Z?

Title: Re: closest product of primes
Post by towr on Jan 17^th, 2007, 10:31am

diff=Z;
P=0, Q=0;
for(i=2; i <= sqrt(Z); i=nextprimeafter(i))
if(Z - i*lastprimebefore(Z/i) < diff)
{
P = i;
Q = lastprimebefore(Z/i);
diff = Z - P*Q;
}
}
printinsomeappropriateformat(P,Q,diff);

Title: Re: closest product of primes
Post by Grimbal on Jan 18^th, 2007, 12:46am

on 01/17/07 at 10:08:07, pharaoh wrote:

I think this is not needed, we can optimize this. What you say? Why check from 2 to Z?

Because I though you said to start it simple, that you want the logic and not optimization. Rereading your post carefully I saw it wasn't quite that. I intentionally made it simple skipping even the most obvious optimizations.

Title: Re: closest product of primes
Post by pharaoh on Jan 18^th, 2007, 1:00am

This should close the topic 8). Not very optimized though.

isPrime(Y)
1. If Y divisible by 2 then Return false 2. Else begin
3. SQRT = Integer(Square Root Of Y)
4. For Counter=3 To Counter=SQRT
5. If Y is divisible by Counter then Return false
6. Increment Counter by 2
7. End of For loop
8. End of Else
9. Return true

closestPrime(Y)
1. Repeat steps 2 and 3
2. If isPrime(Y) then Return Y
3. Else Decrement Y by 1

getClosestToZ(Z)
1. If Z is divisible by 2, then Decrement Z by 1.
2. Initialize array Solution
3. Repeat steps 5 to 28
4. Initialize array ListOfFactors
5. SQRT = Integer(Square Root Of Z)
6. For Counter=3 To Counter=SQRT
7. If isPrime(Counter) Then Add Counter to ListOfFactors
8. Increment Counter by 2
9. End of For loop
10. Difference = Z;
11. Solution[0] = 0
12. Solution[1] = 0
13. If ListOfFactors has atleast one value Then Begin
14. Length = Length(ListOfFactors)
15. For Counter=1 To Counter=Length
16. firstFactor = ListOfFactors[Counter]
17. secondFactor = Integer (Z / firstFactor)
18. secondFactor = closestPrime(secondFactor)
19. If Z - (firstFactor * secondFactor) is less than Difference Then Begin
20. Difference = Z - (firstFactor * secondFactor)
21. Solution[0] = firstFactor
22. Solution[1] = secondFactor
23. End of If
24. Increment Counter by 1
25. End of For loop
26. End of If ListOfFactors...
27. If Difference equals Z Then Decrement Z by 1
28. Else Return Solution

Title: Re: closest product of primes
Post by towr on Jan 18^th, 2007, 2:15am

on 01/18/07 at 01:00:03, pharaoh wrote:

This should close the topic 8). Not very optimized though.

isPrime(Y)

You can improve isPrime by storing old results, that way you only have to test dividing by primes, rather than all odd numbers.

And it makes the rest simpler/faster too.

Title: Re: closest product of primes
Post by pharaoh on Jan 18^th, 2007, 2:17am

on 01/18/07 at 02:15:40, towr wrote:

You can improve isPrime by storing old results, that way you only have to test dividing by primes, rather than all odd numbers.

Yes.

Title: Re: closest product of primes
Post by shishir85 on Feb 7^th, 2007, 10:28pm

on 01/17/07 at 06:14:43, pharaoh wrote:

A simple one..

Given any number Z, write a program to find two prime numbers whose product is closest to Z, and is not greater than or equal to Z.

What if we modify the original question and remove the condition that the product has to be smaller than Z.
New Question:
Given any positive integer Z (Z > 3), find two prime numbers A,B whose product is closest to Z.
| Z - A*B | should be smallest.