c - Did I just prove that sieve of Eratosthenes is less efficient than trial division? -

i trying compare run-time speed of 2 algorithms: brute-force c program print prime numbers (10,000 numbers), , sieve of eratosthenes c program (also 10,000 prime numbers).

my measured run-time sieve algorithm was: 0.744 seconds

my measured run-time brute-force algorithm was: 0.262 seconds

however, told sieve of eratosthenes algorithm more efficient brute-force method, , thought run faster. either i'm wrong or program flawed (which doubt).

therefore, question is: since got opposite results expected, prove sieve of eratosthenes less efficient algorithm in terms of speed, compared trial division?

i'm not sure if of relevance, i'm using dev c++ compiler , windows 7.

tl;dr: comparing speed of code variants @ 1 input size meaningless; comparing empirical orders of growth reflects algorithmic nature of code , consistent across different test platforms, same test range of input sizes. comparing absolute speed values meaningful code variants exhibit same asymptotic or @ least local growth behaviour.

---

it not enough measure speed of 2 implementations @ 1 input size. several data points needed, assess run time empirical orders of growth of our code (because code can run varying input sizes). found logarithm of ratio of run times, in base of ratio of input sizes.

so if @ input code_1 runs 10 times faster code_2, run time doubles each doubling of input size, whereas code_2 grows 1.1x, code_2 become much faster code_1.

so real measure of algorithm's efficiency run time complexity (and complexity of space i.e. memory requirements). , when measure empirically, measure if particular code @ hand (at particular range of input sizes), not algorithm itself, i.e. ideal implementation of it.

in particular, theoretical complexity of trial division o(n^1.5 / (log n)^0.5), in n primes produced, seen ~ n^1.40..1.45 empirical order of growth (but can ~n^1.3 initially, smaller input sizes). sieve of eratosthenes o(n log n log (log n)), seen ~ n^1.1..1.2. there sub-optimal implementations of both trial division , sieve of eratosthenes run @ ~n^2.0 , worse.

so no, proves nothing. 1 datapoint meaningless, at least three needed "big picture" i.e. able predict certainty run time ⁄ space needed bigger input sizes.

prediction known certainty scientific method about.

---

btw run times long. calculation of 10,000 primes should instantaneous, less 1/100th of second c program run on fast box. perhaps you're measuring printing time well. don't. :)