I'm testing something to kill time. Can I ask for an efficient Perl, Java, C and C++ implementations of the following Python? (Also, if you have any ideas on how to make this more efficient in Python, you're welcome to own me.)
The first function calculates primes up to max using a classic algorithm. Do not change the algorithm, just try to make the code as fast as possible; tricks allowed as long as you stick to this algorithm.
The second function implements a Sieve of Eratosthenes using dictionaries (hashes), which takes an assload of memory but is much faster. Again, don't change the algorithm, but you can use any data structure you see fit.
tl;dr version: Could you port the following into efficient Perl, Java, C and C++? No need to understand what they do.
def Primes(max):
a = []
for i in xrange(1, max + 1):
prime = True
for j in xrange(2, int(sqrt(i)) + 1):
if not i % j:
prime = False
break
if prime:
a += [i]
return a
def Erat(size):
size1 = size + 1
s = dict.fromkeys(xrange(2, size1), None)
for n in xrange(2, int(sqrt(size)) + 1):
if n in s:
for i in xrange(n << 1, size1, n):
if i in s:
del s[i]
return [1] + list(s)
Name:
Anonymous2006-08-17 19:08
Here's the PHP port of them, as fast as I could get it:
function Primes($max) {
for ($i = 1; $i <= $max; $i++) {
$prime = true;
$limit = (int) sqrt($i);
for ($j = 2; $j <= $limit; $j++)
if (!($i % $j)) {
$prime = false;
break;
}
if ($prime)
$a[] = $i;
}
return $a;
}
std::vector<int> primes(int max) {
std::vector<int> a;
int limit(1);
for (int i(1); i <= max; ++i) {
bool isPrime(true);
int newLimit = limit + 1;
if (newLimit * newLimit <= i) ++limit;
for (int j(2); j <= limit; ++j) {
if (!(i % j)) {
isPrime = false;
break;
}
}
if (isPrime) a.push_back(i);
};
return a;
}
std::vector<int> erat(int size) {
std::vector<int> s(size - 1);
for (int i(2); i <= size; ++i) {
s[i-2] = i;
}
int limit(1);
while (limit * limit < size) ++limit;
for (int n(2); n <= limit; ++n) {
if (s[n-2]) for (int i((n << 1) - 2); i <= size - 2; i += n) {
s[i] = 0;
}
}
std::vector<int> primeList;
primeList.push_back(1);
for (std::vector<int>::iterator it(s.begin()); it != s.end(); ++it) {
if (*it != 0) primeList.push_back(*it);
}
return primeList;
}
Name:
Anonymous2006-08-18 7:37
Perl: sub Primes {
my ($max) = (@_);
foreach $i(1..$max+1) {
$prime = 1;
$limit = int(sqrt($i)) + 1;
foreach $j(2..int(sqrt($i)) + 1) {
unless($i % $j) {
$prime = 0;
last;
}
}
push(@a, $i) if $prime;
}
return @a;
}
I'll post the Erat later if no one beats me to it.
Name:
Anonymous2006-08-18 10:36
break
== goto == FAIL.
also, why do you do you add [1] to the beginning of the array at the end? why not just return s?
and here's Erat in javascript (i know you didn't ask for javascript, but i like javascript): function Erat(size)
{
s=new Array(size);
for(i=2;i<=size;i++)
s[i]=true;
var limit=Math.round(Math.sqrt(size));
for(n=2;n<=limit;n++)
if(s[n])
for(i=n<<1;i<=size;i+=n)
s[i]=null;
return([true].concat(s));
}
Name:
Anonymous2006-08-18 17:20
Thanks! JavaScript is fine too. As for break, gb2/hippy university programming classes. (P.S.: if, else, while, do and for == goto == FAIL.)
I add [1] because 1 is prime and therefore it has to be returned, but the Sieve will not work if I process 1 (it'd mark all numbers and end immediately, concluding everything is prime, as any number, including primes, can be divided by 1). You can see how in the outer for I deliberately skip 1 { for n in xrange(2, ... }.
Name:
Anonymous2006-08-18 17:57
1 is prime
massive fail
Name:
Anonymous2006-08-18 18:03
I add [1] because 1 is prime and therefore it has to be returned, but the Sieve will not work if I process 1 (it'd mark all numbers and end immediately, concluding everything is prime, as any number, including primes, can be divided by 1). You can see how in the outer for I deliberately skip 1 { for n in xrange(2, ... }.
except that 1 is not prime.
and if you add [1] to the beginning of the array, that shifts the other values so that s[3] represents 2, s[4] represents 3, etc.
if you just return s, then s[2] represents 2, s[3] represents 3... much more logical.
Name:
Anonymous2006-08-19 7:21
except that 1 is not prime.
Oops. Turns out it is not. (The definition, as I just checked it, said numbers that have two distinct divisors, while I worked with the definition of numbers that can only be divided by 1 and themselves, which basically had allowed 1.)
and if you add [1] to the beginning of the array, that shifts the other values so that s[3] represents 2, s[4] represents 3, etc.
list(s) is [2, 3, 5, 7, 11, 13...], adding 1 it was [1, 2, 3, 5, 7, 11, 13...]; either way s[x] is not meant to be x.
Name:
aWi2006-08-19 8:58
this code would be very inefficient for large n..
its a basic seiving method...
while not entirely accurate, Fermats test would be more suitable for large primes.
there are better seiving methods, but either way they are non-polynomial in time complexity.
Name:
Anonymous2006-08-19 9:24
>>11
Sure, I'm just comparing some languages. I could have used the sieve of Atkin but I wanted it simple (but as fast as a particular algorithm can get in a language).
Name:
Anonymous2006-08-19 10:00
OCAML
open Bigarray
let set_false (a:(int, int8_unsigned_elt, c_layout) Array1.t) i =
let ic = i lsr 3 in
let v = a.{ic} in
let bit = v land lnot(1 lsl (i land 0x7)) in
if v <> bit then a.{ic} <- bit
let erat m =
let a = Array1.create int8_unsigned c_layout ((m lsr 3) + 1) in
Array1.fill a 0xFF;
let count = ref 0 in
for i = 2 to m - 1 do
if a.{i lsr 3} land (1 lsl (i land 0x7)) > 0 then
(let j = ref(2*i) in
while !j < m do set_false a !j; j := !j + i done;
incr count)
done;
!count
Name:
Anonymous2006-08-19 11:18
>>10
oh, the way i did it in javascript, s is [,,true,true,,true,,true,,,,true,,true...]. i based that on >>2's php version because i don't know enough python to figure out what your code does.
why put the numbers in the array if you can use the array indexes to check if a number is prime? 'if(s[number])' is a lot simpler and faster than searching the array to see if a number is in it.
i guess there's not really any reason not to in the javascript version, though, since it just requres changing the "s[i]=true;" line to "s[i]=i;". i'd think it would be a huge performance hit in php, though (needing to use a for loop instead of array_fill).
>>15
It's not homework stupid; in what programming class do you get teached half a dozen languages and care about implementation efficiency? And what programming class guy asks for Java implementations of something he did in Python?
Name:
Anonymous2006-08-20 20:05
>>16
someone who is only fluent in Python is taking a programming class that teaches Java. the request for efficiency would either imply that bonus credit would be given for the best code, or OP is trying to suck up to the professor for potential employment references. the request for other languages is merely obfuscation for the true intent.
Name:
Anonymous2006-08-21 2:39
>>17
Nice theory, only not true, plus it has a major flaw: Who in his sane mind would learn Java being fluent in Python? That's like saying, I'm used to fucking hot Japanese chicks, please tell me how to fuck fat women.
template <typename T>
bool Math::isPrime(T n) {
if (n <= 1)
return false;
if ((n % 2) == 0 && n > 2)
return false;
if ((n % 3) == 0 && n > 3)
return false;
if (((n % 6) != 1 && (n % 6) != 5) && n > 5)
return false;
if (sizeof(T) <= 4) {
uint32 b = static_cast<uint32>(sqrt((float)(n)));
for (uint32 c = 3; c <= b; c += 2) {
if ((n % c) == 0) {
return false;
break;
}
}
}
else {
uint64 b = static_cast<uint64>(sqrt((double)(n)));
for (uint64 c = 3; c <= b; c += 2) {
if ((n % c) == 0) {
return false;
break;
}
}
}
return true;
}
Name:
Anonymous2009-12-18 1:12
RAII is the heartiest, chunkiest, and most delicious of programming metaphors. Every day I write two bowls full of RAII. Broccoli and cheese is my favorite kind but usually I get tomato, because if I eat too much broccoli, I hax myself. The tomato is very good as well, though. It has actual chunks of tomato, which is not something you'll find in a typical programming metaphor. The thought of those tomato chunks on my keyboard is enough to make my mouth water. Another good kind that I like is beef and barley. The beef has to be manually managed but the broth and the barley make up for it. Basically RAII is something everyone should try once, even if it kills them. My brother worked on a prototype of the THERAC-25 and he died of RAII, but his last words were "It was delicious."
Name:
Anonymous2009-12-18 10:14
I don't know what pathetic math teachers you guys had, but 2 is prime.
Bringing /prog/ back to its people
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy
All work and no play makes Jack a dull boy