The Sieve of Eratosthenes is best for finding prime
On Mon, Apr 12, 2010 at 10:58 AM, BlackdiamonD patidarc...@gmail.comwrote:
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in
thankx for u r reply.in my code i implemented Sieve of Eratosthenesthat
but some type of optimization were required that i have done...got accepted.
On Wed, Apr 14, 2010 at 2:57 PM, Ashish Mishra amishra@gmail.comwrote:
The Sieve of Eratosthenes is best for finding prime
On Mon, Apr
thank kartik thanks but it was with lot of optimized code i was unable to
understand though i have changed my code more know it is taking around 8 to
8.5 seconds in my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int
http://wwwhomes.uni-bielefeld.de/achim/prime_sieve.html
take a look at this link . The running time is less than 2 sec for 10^8.
On Sun, Apr 11, 2010 at 2:38 AM, Black Diamond patidarc...@gmail.comwrote:
i have an problem on SPOJ to find all the prime less than 10^8
Hi, Black DiamonThere is a trick that number that can be devided by 2 or 3
is ignored, so we just deal with number 6n + 1 and 6n + 5, so you can try
this:
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
int table = 4;
Not only even numbers, but you can extend the algorithm for other numbers as
well.
Start with 2, mark all the numbers which are multiples of 2,
then in the next iteration, take 3, and mark all the numbers which are
multiples of 3.
If a number is already marked, you dont consider that number in
i have an problem on SPOJ to find all the prime less than 10^8
https://www.spoj.pl/problems/TDPRIMES/
i am using sieve of erastosthenes algorithm to find primes
my code is taking in my machine around 10.9 to 11.2 seconds
and time limit is 10 second how i can change my code or any diff logic..???
why don't you remove all even numbers from consideration and add 2
explicitly. I think that would help.
--
Rohit Saraf
Second Year Undergraduate,
Dept. of Computer Science and Engineering
IIT Bombay
http://www.cse.iitb.ac.in/~rohitfeb14
On Sun,