Problem 187

[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.

[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.

[dmj1066]

Got it, thanks.

[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]

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]

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.

[whatteaux]

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]

Indeed, I'm not quite sure what thundre was thinking. Counting semiprimes is exactly what you should be doing; not numbers like 12.

[thundre]

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.

[Oliver1978]

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