Re: [algogeeks] Finding all prime less than 10^8
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 my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy
karthik.gin...@gmail.comwrote:
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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ashish Mishra
http://ashishmishra.weebly.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
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 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 my computer but still i am getting TLE on server
#includestdio.h
#define ten8 (1)
const int mod=32;
unsigned int M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy
karthik.gin...@gmail.comwrote:
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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ashish Mishra
http://ashishmishra.weebly.com/
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
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 M[ten8/mod];
int main()
{
int half=1, i,j,x=1;
int y=ten8/mod;
freopen(output.txt,wt,stdout);
for ( i = 0;i y;i++)
M[i] = 0;
printf(2\n);
for ( i = 3;i ten8;i+=2)
{
int a=i/mod,b=i%mod;
if (((M[a]b)1)==0)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j/mod] =M[j/mod]|(1(j%mod));
}
}
}
}
On Sun, Apr 11, 2010 at 7:20 AM, Karthik Reddy karthik.gin...@gmail.comwrote:
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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Ram Karthik Reddy Ginuga
karthik.ginuga[at]gmail.com
CCNA,MCP
Mozilla Campus Ambassador
SPOJ world rank #1088
http://www.spoj.pl/users/karthu/
(91)40 27425999
(91)9247818845
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] Finding all 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;
for ( i = 0;i ten8;i++)
M[i] = false;
printf(2\n);
x = 2; // 2 and 3 are prime number;
for (i = 5;i ten8;table = 6 - table, i += table) //only deal with 6n
+ 1 and 6n + 5
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
On Sun, Apr 11, 2010 at 5:08 AM, Black Diamond patidarc...@gmail.comwrote:
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
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 the
consequent iterations, in our case, you skip marking the numbers which are
multiples of 4, since 4 is already marked, all the multiples of 4 will also
be marked.
Ex: to find all the prime numbers till 20.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0 Iteration = n/2
first iteration for 2, mark: 4,6,8,10,12,14,16,18,20
2nd iteration for 3, mark: 6,9,12,15,18
3rd iteration for 4, skip this iteration, since 4 is already marked,
4th iteration for 5, mark: 10, 15, 20
5th iteration for 6, skip
6th iteration for 7, mark: 14
7th iteration for 8, skip
8th iteration for 9, skip
9th iteration for 10, skip
remaining numbers are prime numbers.
On Sun, Apr 11, 2010 at 10:24 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
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/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14
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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Thanks Regards,
- NMN
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
[algogeeks] Finding all prime less than 10^8
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups Algorithm
Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
attachment: My+Sign.JPG
Re: [algogeeks] Finding all prime less than 10^8
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, 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
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..???
//-//
#includecstdio
using namespace std;
#define ten8 (1)
bool M[ten8];
int main()
{
int half=1, i,j,x=0;
for ( i = 0;i ten8;i++)
M[i] = false;
for ( i = 2;i ten8;i++)
{
if (M[i] == false)
{
x++;
if(x%100==1)
printf(%d\n,i);
if(ihalf)
continue;
for (int j = i * i;j ten8;j += i)
{
M[j] = true;
}
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
My+Sign.JPG
