J, 50 40 38 37 characters
f=:3 :'+/y<:}.~.,(~:/**/)~p:i._1&p:y' Usage:
f 1 0 f 62 18 f 420 124 f 10000 2600 With thanks to FUZxxl.
Performance test
showtotal_jpm_ ''[f 1[start_jpm_ '' Time (seconds) ┌───────┬──────┬────────┬────────┬─────┬────┬───┐ │name │locale│all │here │here%│cum%│rep│ ├───────┼──────┼────────┼────────┼─────┼────┼───┤ │f │base │0.000046│0.000046│100.0│100 │1 │ │[total]│ │ │0.000046│100.0│100 │ │ └───────┴──────┴────────┴────────┴─────┴────┴───┘ showtotal_jpm_ ''[f 1[f 62[start_jpm_ '' Time (seconds) ┌───────┬──────┬────────┬────────┬─────┬────┬───┐ │name │locale│all │here │here%│cum%│rep│ ├───────┼──────┼────────┼────────┼─────┼────┼───┤ │f │base │0.000095│0.000095│100.0│100 │2 │ │[total]│ │ │0.000095│100.0│100 │ │ └───────┴──────┴────────┴────────┴─────┴────┴───┘ showtotal_jpm_ ''[f 1[f 62[f 420[start_jpm_ '' Time (seconds) ┌───────┬──────┬────────┬────────┬─────┬────┬───┐ │name │locale│all │here │here%│cum%│rep│ ├───────┼──────┼────────┼────────┼─────┼────┼───┤ │f │base │0.000383│0.000383│100.0│100 │3 │ │[total]│ │ │0.000383│100.0│100 │ │ └───────┴──────┴────────┴────────┴─────┴────┴───┘ showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[start_jpm_ '' Time (seconds) ┌───────┬──────┬────────┬────────┬─────┬────┬───┐ │name │locale│all │here │here%│cum%│rep│ ├───────┼──────┼────────┼────────┼─────┼────┼───┤ │f │base │0.084847│0.084847│100.0│100 │4 │ │[total]│ │ │0.084847│100.0│100 │ │ └───────┴──────┴────────┴────────┴─────┴────┴───┘ showtotal_jpm_ ''[f 1[f 62[f 420[f 10000[f 50000[start_jpm_ '' Time (seconds) ┌───────┬──────┬────────┬────────┬─────┬────┬───┐ │name │locale│all │here │here%│cum%│rep│ ├───────┼──────┼────────┼────────┼─────┼────┼───┤ │f │base │5.014691│5.014691│100.0│100 │5 │ │[total]│ │ │5.014691│100.0│100 │ │ └───────┴──────┴────────┴────────┴─────┴────┴───┘ I'm no theoretician as has been seen here in the past, but I think the time complexity is something like O(np2) where np is the number of primes up to and including the input number n. This is based on the assumption that the complexity of my method (generating a very large multiplication table) far outweighs the complexity of the prime generating function built in to J.
Explanation
f=:3 :'...' declares a (monadic) verb (function). The input to the verb is represented by y within the verb definition.
p:i._1&p:y The p: verb is the multi purpose primes verb, and it's used in two different ways here: _1&p:y returns the number of primes less than y then p:i. generates every one of them. Using 10 as input:
p:i._1&p:10 2 3 5 7 (~:/**/)~ generates the table I spoke of earlier. */ generates a multiplication table, ~:/ generates a not-equal table (to eliminate the squares) and both of these are multiplied together. Using our previous output as input:
*/~2 3 5 7 4 6 10 14 6 9 15 21 10 15 25 35 14 21 35 49 ~:/~2 3 5 7 0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0 (~:/**/)~2 3 5 7 0 6 10 14 6 0 15 21 10 15 0 35 14 21 35 0 }.~., now we turn the numbers into one list , get the unique values ~. and remove the 0 at the start }.
}.~.,(~:/**/)~2 3 5 7 6 10 14 15 21 35 y<: a comparison with the original input to check which values are valid:
10<:6 10 14 15 21 35 1 1 0 0 0 0 +/ and then sum that to get the answer.
+/1 1 0 0 0 0 2 