Jump to content

Challenge: Sieve of Eratosthenes, in PHP


ShadowMage

Recommended Posts

Ok, let's see how many people we can get in on this one. I think this should be fairly easy.Replicate the Sieve of Eratosthenes using PHP. EDIT: Suppose I should clarify that you need to construct an array of all prime numbers less than or equal to $n.Whoever can build the most efficient (in terms of memory usage and speed) version wins. Deadline is midnight Thursday. (US Central time)

Link to comment
Share on other sites

  • Replies 55
  • Created
  • Last Reply
I'll wait before posting, but I have a Sieve of Eratosthenes that requires 17 statements, not including function declarations or the statement that invokes it. :)
Hey, mine's actually shorter!? (16 statements :) ) Wow! But we'll have to wait and see who's is faster...
Link to comment
Share on other sites

My preliminary solution is 7 statements long :). I'm sure I can make it a bit shorter.I think speed is a more pertinent issue - programs can be made as short as people want. We recently had a project for one of my subjects - a program in Python - most people's solutions were ~100 lines long, but I managed to squeeze everything into one line :). Of course, it was horribly inefficient and repetitive.Edit: times - my solution takes ~11 seconds to do 1000 iterations of the Sieve to 100. 10 iterations to 1000 takes ~20 seconds. P.S. my solution scales badly, because it has to copy out the entire list for every iteration.

Link to comment
Share on other sites

Yeah, per my rules for the "title" context, I am counting statements, not lines. Thus:++i;i = Math.abs(i);is two statements, but so isi = Math.abs(++i);I have no interest in a contest for writing the most terse code possible. I am not programming a Commodore 64.

Link to comment
Share on other sites

Hmm, so how many statements would the following be?

do {	if ($test < 1) {		$b++;	}} while ($i < $a);

Link to comment
Share on other sites

Besides, my rules didn't include least amount of statements. :) Only efficiency (memory and speed, though it'll be hard for me to test memory usage since the memory_get_usage function doesn't seem to exist in the PHP setup here at work)EDIT: Synook, I would count that as three statements:

for ($i in $a) { //1	if ($test < 1) { //2		$b++; //3	}}

Link to comment
Share on other sites

One person needs to test all the solutions, or else someone could just use a super-powerful computer. Are we going to test scalability (e.g. efficiency for different sizes) as well?P.S. under DD's rules my code is still 7 statements (not counting the return). :)P.P.S. whoops, I edited my previous post after you posted your response. I'm counting the do...while by itself as one statement.

Link to comment
Share on other sites

One person needs to test all the solutions, or else someone could just use a super-powerful computer. Are we going to test scalability (e.g. efficiency for different sizes) as well?P.S. under DD's rules my code is still 7 statements (not counting the return). :)
I agree, one person will need to test the solutions. I can test speed, but I cannot test memory usage so I may drop memory usage from the rules.I'm not 100% sure what scalability means. Whether it's tested or not, I guess would depend on how easy it would be to test. :)Still 7 statements, eh? Interesting....I'm curious to see what that looks like. :( (BTW, mine is 15 not counting the return)EDIT: :) Editing.......Yeah, I'd count the do/while as a single statement, too.
Link to comment
Share on other sites

If we have not done so, we are quickly going to break the spirit of the original proposal. I suspect OP had simple tasks and simple judging criteria in mind.I would say a while and a do-while are each a single statement (no counting the statements inside the loop, of course). A better question for debate is whether a for-loop initializer counts as 1 or 3 statements (assuming you fill all 3 placeholders).FWIW, I have been counting return statements. But 7 is interesting. This is not a matter of economizing my code, but taking a whole other approach.

Link to comment
Share on other sites

As in, what sort of time complexity the algorithm runs in. For example, a solution that has complexity O(n) will be much faster as the number of primes increases versus a function that had complexity O(n2).Edit: this means that while there may be little difference between the two functions if we calculate the sieve to 100, there would be if we did to 1000.Edit2: I think it should count as three statements.Edit3: what about nested function calls, e.g. f(g(h($i)))?Edit4: Whoops, mis-calculated, it's actually 8. :)

Link to comment
Share on other sites

I did notice a glaring inefficiency in my code that I repaired with no added statements. (Or maybe there was one.) With each iteration, the sieve requires you to test the next number in the list. But of course the list gets smaller with each iteration. My original loop counter was simply incrementing by 1. The result was the same (reducing the list to just the primes) but the number of iterations in this process was double or triple the number that is actually required. I didn't even realize it until I decided to alert the list with every iteration. Lesson learned.

Link to comment
Share on other sites

Nested calls is exactly what I'm talking about. Each call is a statement.If we didn't do that, we would have to resort to some serious benchmarking. I personally don't run PHP on my desktop, so I am coding all this in JavaScript. (PHP would simplfiy a few things, so maybe I'll migrate.) So now we have to benchmark on 3-4 platforms, 4-5 browsers, and an untold number of processors. And even if we did use server-side environments, we still have the matter of which environment, which platform and which hardware being used.Counting statements makes for a much friendlier (and more manageable) contest, I think.

Link to comment
Share on other sites

Ok, my code, in its absolute most expanded form, such that every line contains no more than, besides variables and literals, one:(assignment or control structure) and (operator or function call)contains 14 statements. This is fun!

Link to comment
Share on other sites

Okay, looking at Shadows edit in Post #1, I want to make sure we're still building a Sieve of Eratosthenes, not simply a prime number generator. Perhaps the Sieve of Eratosthenes really is the most efficient tool for this. I just want clarification that this is the tool we're building.Like, if a version of PHP came out today that has an is_prime function, well, the code would get simple indeed, and we'd all write it the same way, I'm sure.

Link to comment
Share on other sites

Okay, looking at Shadows edit in Post #1, I want to make sure we're still building a Sieve of Eratosthenes, not simply a prime number generator. Perhaps the Sieve of Eratosthenes really is the most efficient tool for this. I just want clarification that this is the tool we're building.Like, if a version of PHP came out today that has an is_prime function, well, the code would get simple indeed, and we'd all write it the same way, I'm sure.
Yes, we are building the sieve, which should be constructing an array of the primes that are less than or equal to a number. From my understanding, that is what the sieve does, is it not?EDIT: We're not building a simple is_prime function. That would indeed be very simple.
Link to comment
Share on other sites

Alright, in it's absolute absolute most expanded form, such that it is not possible to expand it any more (e.g. no for or foreach structures, and if(!($a > b || $c < $d) is five statements), my code has 21 statements.P.S. I think using is_prime() would be cheating - we'd actually need to implement the Sieve algorithm, including things such as only counting until p2>n.

Link to comment
Share on other sites

Ouch. I forgot about combining comparisons in a conditional. The convenience of certain operators is easy to take for granted, especially when they form the basis of the underlying engineering (eg: and, or, xor).

Link to comment
Share on other sites

I think using is_prime() would be cheating - we'd actually need to implement the Sieve algorithm, including things such as only counting until p2>n.
Yes, exactly. That's what I had in mind when I posted the challenge.EDIT: How many statements would you count each of these as:while (count($arrSieve) < $n-1) {while ($arrSieve[$index] <= sqrt($n)) {foreach ($arrSieve as $i => $num) {I counted them each as one, but I'm not sure.
Link to comment
Share on other sites

Well, try the "expand-until-not-possible" method :). That's what I did to my code.For example:

while (count($arrSieve) < $n-1) {

becomes:

$count = count($arrSieve);$n_minus_one = $n - 1;$more = $count < $n_minus_one;while ($more) {

(Four statements)

foreach ($arrSieve as $i => $num) {

becomes:

do {	$e = each($arrSieve);	if ($e) {		$i = $e[0];		$num = $e[1];		// (inside code here)	}} while ($e);

(5 statements) Edit: you may be able to think of more efficient ways of doing this based on your code.

Link to comment
Share on other sites

How about we forgo the "contest" part of this contest, and just post our respective solutions so we can discuss them? Then we can go into whatever challenge we think of next fully understanding what we have to do.

Link to comment
Share on other sites

How about we forgo the "contest" part of this contest, and just post our respective solutions so we can discuss them? Then we can go into whatever challenge we think of next fully understanding what we have to do.
That might be a good idea. So long as a victor is still named. :)
Link to comment
Share on other sites

$x = count($arrSieve);$y = $n-1;while ($x < $y)Three statements. I suppose we could get nasty and require this:$my_boolean = $x < $y;while($my_boolean)bring the total up to 4, but that's just stoopid and wouldn't make a difference in the results.

Link to comment
Share on other sites

Archived

This topic is now archived and is closed to further replies.


×
×
  • Create New...