Problem 187

A place to air possible concerns or difficulties in understanding ProjectEuler problems. This forum is not meant to publish solutions. This forum is NOT meant to discuss solution methods or giving hints how a problem can be solved.
Forum rules
As your posts will be visible to the general public you
are requested to be thoughtful in not posting anything
that might explicitly give away how to solve a particular problem.

This forum is NOT meant to discuss solution methods for a problem.

In particular don't post any code fragments or results.

Don't start begging others to give partial answers to problems

Don't ask for hints how to solve a problem

Don't start a new topic for a problem if there already exists one


See also the topics:
Don't post any spoilers
Comments, questions and clarifications about PE problems.
Post Reply
dmj1066
Posts: 4
Joined: Tue Apr 21, 2009 1:08 am

Problem 187

Post by dmj1066 »

Hi,
I was fairly confident that my method for this was correct but my answer is not correct. The problem is to find the number of "semi-primes"< 10^8. The example given shows there are 10 that are < 30 (4, 6, 9, 10, 14, 15, 21, 22, 25, 26)
My answers for smaller numbers than 10^8 are:

34 for <100
199 for < 1000
210035 for < 10^6
and my answer for <10^8 ends in 24 (ie ...24).

I am wondering if there is an error in my list of prime numbers. Any thoughts appreciated.
User avatar
rayfil
Administrator
Posts: 1406
Joined: Sun Mar 26, 2006 5:30 am
Location: Quebec, Canada
Contact:

Re: Problem 187

Post by rayfil »

Your results for <100 and <10^6 are correct. Your result for <1000 is not correct but may only be due to a typo error on one of the digits.
The result for <10^7 ends in ....24.
When you assume something, you risk being wrong half the time.
dmj1066
Posts: 4
Joined: Tue Apr 21, 2009 1:08 am

Re: Problem 187

Post by dmj1066 »

Got it, thanks.
NotMyFault
Posts: 4
Joined: Sun Apr 17, 2011 8:58 pm

Re: Problem 187

Post by NotMyFault »

bumped to not make a new topic. I've got a similar problem. My method is to generate all primes, then have a set of all multiples of them. Then test this subset. I'm annoyed because I can't see the mistake in my code. I know it wouldn't be the fastest, but it should work. (I've got the same output up to 10^6 given above)
Oiler
Posts: 1
Joined: Mon Apr 23, 2012 11:38 pm

Re: Problem 187

Post by Oiler »

I used http://en.wikipedia.org/wiki/Prime-coun ... .80.28x.29 and http://mathworld.wolfram.com/Semiprime.html, but my answer for 10^8 is wrong. (I brute forced the solution originally) Would anyone like to check my code? (PM me)
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 187

Post by thundre »

Oiler wrote:I used http://en.wikipedia.org/wiki/Prime-coun ... .80.28x.29 and http://mathworld.wolfram.com/Semiprime.html, but my answer for 10^8 is wrong. (I brute forced the solution originally) Would anyone like to check my code? (PM me)
Incorrect advice hidden. Don't look. Pretend I never wrote it.
Expand
If your idea is based on counting semi-primes, it's probably wrong. 12 is not a semi-prime, but it does have exactly 2 prime factors.
Last edited by thundre on Fri Nov 23, 2012 10:50 pm, edited 1 time in total.
Image
whatteaux
Posts: 7
Joined: Mon Sep 24, 2012 11:58 am

Re: Problem 187

Post by whatteaux »

thundre wrote:If your idea is based on counting semi-primes, it's probably wrong. 12 is not a semi-prime, but it does have exactly 2 prime factors.
This makes it even more confusing. The title of the problem is "Semi-primes" (the text that pops up when I hover over it in the 'progress' view). In the example given (the set of valid composites below 30) 12 is omitted. If, by your reasoning, 12 has 2 prime factors, then 25 has 1 prime factor (wrong, according to the example given) and 18 (2 x 3 x 3) also has only 2 prime factors (wrong, according to the example) as does 20, etc..

I don't want to sound incredulous, but I just don't believe you.
TripleM
Posts: 382
Joined: Fri Sep 12, 2008 3:31 am

Re: Problem 187

Post by TripleM »

Indeed, I'm not quite sure what thundre was thinking. Counting semiprimes is exactly what you should be doing; not numbers like 12.
thundre
Posts: 356
Joined: Sun Mar 27, 2011 10:01 am

Re: Problem 187

Post by thundre »

TripleM wrote:Indeed, I'm not quite sure what thundre was thinking. Counting semiprimes is exactly what you should be doing; not numbers like 12.
Doh! I read the problem wrong that time through. My apologies.
Image
User avatar
Oliver1978
Posts: 166
Joined: Sat Nov 22, 2014 9:13 pm
Location: Erfurt, Germany

Re: Problem 187

Post by Oliver1978 »

rayfil wrote:Your results for <100 and <10^6 are correct. Your result for <1000 is not correct but may only be due to a typo error on one of the digits.
The result for <10^7 ends in ....24.
The same here, I also have receive all the correct numbers, like posted above. Additionally I get 6265 for < 25000. If that's correct I don't seem to see my error. Mind if anybody could take a look at my code?

edit

Solved. Only a little typo :roll:
49.157.5694.1125
Post Reply