Author |
Topic: closest product of primes (Read 824 times) |
|
pharaoh
Newbie
Gender: 
Posts: 50
|
 |
closest product of primes
« on: Jan 17th, 2007, 6:14am » |
 Quote  Modify
|
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.
|
| « Last Edit: Jan 17th, 2007, 6:17am by pharaoh » |
 IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: closest product of primes
« Reply #1 on: Jan 17th, 2007, 9:06am » |
Quote Modify
|
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  Z
|
| « Last Edit: Jan 17th, 2007, 9:07am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: closest product of primes
« Reply #2 on: Jan 17th, 2007, 9:36am » |
Quote Modify
|
"What do we do for Z is 1,2,3 ?"
Forget them. 
"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.
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: closest product of primes
« Reply #3 on: Jan 17th, 2007, 9:39am » |
Quote Modify
|
on Jan 17th, 2007, 9:36am, 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: closest product of primes
« Reply #4 on: Jan 17th, 2007, 9:44am » |
Quote Modify
|
And to test a number for primality it is good to have a list of smaller primes around.
|
|
IP Logged |
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: closest product of primes
« Reply #5 on: Jan 17th, 2007, 9:49am » |
Quote Modify
|
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 
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: closest product of primes
« Reply #6 on: Jan 17th, 2007, 10:03am » |
Quote Modify
|
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.
|
| « Last Edit: Jan 17th, 2007, 10:03am by Grimbal » |
IP Logged |
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: closest product of primes
« Reply #7 on: Jan 17th, 2007, 10:08am » |
Quote Modify
|
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?
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: closest product of primes
« Reply #8 on: Jan 17th, 2007, 10:31am » |
Quote Modify
|
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);
|
| « Last Edit: Jan 17th, 2007, 10:34am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: closest product of primes
« Reply #9 on: Jan 18th, 2007, 12:46am » |
Quote Modify
|
on Jan 17th, 2007, 10:08am, 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.
|
|
IP Logged |
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: closest product of primes
« Reply #10 on: Jan 18th, 2007, 1:00am » |
Quote Modify
|
This should close the topic . 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
|
|
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: closest product of primes
« Reply #11 on: Jan 18th, 2007, 2:15am » |
Quote Modify
|
on Jan 18th, 2007, 1:00am, pharaoh wrote:This should close the topic . 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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
pharaoh
Newbie
Gender:
Posts: 50
|
|
Re: closest product of primes
« Reply #12 on: Jan 18th, 2007, 2:17am » |
Quote Modify
|
on Jan 18th, 2007, 2:15am, 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.
|
| « Last Edit: Jan 18th, 2007, 2:18am by pharaoh » |
IP Logged |
Cogito ergo sum.
-Pharaoh
|
|
|
shishir85
Newbie
 
Gender:
Posts: 19
|
|
Re: closest product of primes
« Reply #13 on: Feb 7th, 2007, 10:28pm » |
Quote Modify
|
on Jan 17th, 2007, 6:14am, 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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print