Rules are simple:
- First n primes (not primes below n), should be printed to standard output separated by newlines (primes should be generated within the code)
- primes cannot be generated by an inbuilt function or through a library, i.e. use of a inbuilt or library function such as, prime = get_nth_prime(n), is_a_prime(number), or factorlist = list_all_factors(number) won't be very creative.
Scoring - Say, we define Score = f([number of chars in the code]), O(f(n)) being the complexity of your algorithm where n is the number of primes it finds. So for example, if you have a 300 char code with O(n^2) complexity, score is 300^2 = 90000, for 300 chars with O(n*ln(n)), score becomes 300*5.7 = 1711.13 (let's assume all logs to be natural logs for simplicity)
Use any existing programming language, lowest score wins
Edit: Problem has been changed from finding 'first 1000000 primes' to 'first n primes' because of a confusion about what 'n' in O(f(n)) is, n is the number of primes you find (finding primes is the problem here and so complexity of the problem depends on the number of primes found)
Note: to clarify some confusions on complexity, if 'n' is the number of primes you find and 'N' is the nth prime found, complexity in terms of n is and N are not equivalent i.e. O(f(n)) != O(f(N)) as , f(N) != constant * f(n) and N != constant * n, because we know that nth prime function is not linear, I though since we were finding 'n' primes complexity should be easily expressible in terms of 'n'.
As pointed out by Kibbee, you can visit this site to verify your solutions (here, is the old google docs list)
Please Include these in your solution -
what complexity your program has (include basic analysis if not trivial)
character length of code
the final calculated score
This is my first CodeGolf Question so, if there is a mistake or loophole in above rules please do point them out.
1[\p:i.78498my answer for this would be
1[\p:i.1000000. Even assuming that J's internal prime algorithm is O(n^2) my score would still only be 196. \$\endgroup\$
nis the number of primes or the maximum prime, and everyone ignores the fact that addition of numbers in the range
O(logn), and multiplication and division are even more expensive. I suggest that you give some example algorithms along with their correct complexity. \$\endgroup\$
O-tilde(k^6). This leads to the implication that anyone who claims a running time better than
O-tilde(n ln n (ln(n ln n))^6)has misunderstood some part of the problem; and to the question as to how
O-tildecomplexities should be handled in the scoring. \$\endgroup\$