[algogeeks] Re: Prime numbers
_(n,1,n,0) is true if n is prime. I set out to create an O(n^n) algorithm. It essentially computes the product of every possible set of n integers in the range (1..n-1). If any of those products equal n, the number is composite. You will notice that the program does not use the * operator to perform a multiplication. It does use * as a logical AND, but to do the products it uses a recursive call with t=1, which is a flag to tell _ to do multiplication instead of determining if n is prime. It does the multiplication by recursively adding up m*n ones. As a result, it takes billions of recursive calls to determine that 6 is not prime. Don On Aug 17, 10:33 am, Sanjay Rajpal wrote: > @Don : can you plz explain it ? > > Sanjay Kumar > B.Tech Final Year > Department of Computer Engineering > National Institute of Technology Kurukshetra > Kurukshetra - 136119 > Haryana, India -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime numbers
@Don : can you plz explain it ? Sanjay Kumar B.Tech Final Year Department of Computer Engineering National Institute of Technology Kurukshetra Kurukshetra - 136119 Haryana, India -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime numbers
I wrote it. Can you figure out how it works?
Don
On Aug 17, 1:25 am, Nitin Nizhawan wrote:
> Hi Dod,
>
> Could you pls expalin what this algorithm is doing and from where you got
> it.
>
> Thanks
> Nitin
>
> On Wed, Aug 17, 2011 at 2:56 AM, Don wrote:
> > I wrote a program to print prime numbers, but it is not very fast. Can
> > someone help me figure out why?
>
> > #include
>
> > /* This program implements a blindingly fast algorithm
> > to find prime numbers, using an elegant recursive method. */
> > int _(int n, int m, int d, int t=0)
> > {
> > int r;
> > if (t) return d?1+_(n,m,d-1,d):n?_(n-1,m,m,n):0;
> > for(r=m!=n; d*(t > r &= _(n,_(t,m,0,1),d-1)|!_(t,1,t);
> > return r*n;
> > }
>
> > /*--
> > Print primes up to the requested value
> > */
> > int main(int argc, char* argv[])
> > {
> > for(int n = 2; n <= 1000; n++)
> > printf("%d is%s prime\n",n, _(n,1,n,0)?"":" not");
>
> > return 0;
> > }
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@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.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime Numbers
Do take a look at this also
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes#cite_note-7
Source code to list all prime numbers till number n
#include
#include
#define bool int
using namespace std;
int main(){
int n;
cin>>n;
int i,j;
bool primeValues[1000]={0};
for(i=4;i<=n;i=i+2){
primeValues[i] = 1;
}
for(i=3;i*i<=n;i=i+2){
for(j=2;j wrote:
> thanq u very much
>
> On Jul 23, 10:13 pm, arun kumar wrote:
> > hope this link will help youhttp://
> www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTes...
> >
> >
> >
> >
> >
> >
> >
> > On Sat, Jul 23, 2011 at 10:39 PM, frank wrote:
> > > what is the efficient algorith to find the prime numbers or to check a
> > > number prime or not ?
> > > Helpful if the pseudo code provided.
> >
> > thank you
> >
> > > --
> > > You received this message because you are subscribed to the Google
> Groups "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com.
> > > For more options, visit this group athttp://
> 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 algogeeks@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.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
thanq u very much On Jul 23, 10:13 pm, arun kumar wrote: > hope this link will help > youhttp://www.topcoder.com/tc?module=Static&d1=tutorials&d2=primalityTes... > > > > > > > > On Sat, Jul 23, 2011 at 10:39 PM, frank wrote: > > what is the efficient algorith to find the prime numbers or to check a > > number prime or not ? > > Helpful if the pseudo code provided. > > thank you > > > -- > > You received this message because you are subscribed to the Google Groups > > "Algorithm Geeks" group. > > To post to this group, send email to algogeeks@googlegroups.com. > > To unsubscribe from this group, send email to > > algogeeks+unsubscr...@googlegroups.com. > > For more options, visit this group > > athttp://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 algogeeks@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.
[algogeeks] Re: Prime Numbers
Okay I got it myself
@OP
This can be done in O(n*k*logn)
where k is of order 10^3 at the very max , when u need a prime like 1
trillion
On Jan 28, 6:44 pm, sankalp srivastava
wrote:
> Correct me if I'm wrong , but according to you , will this be the
> approach ?
>
> boolean array[10];
> int primes[100];
> void seive()
> {
> int index=0;
> for(int i=2;i*i<10;i++)
> {
> if(isprime[i])
> {
> primes[index++]=i;
> for(int j=i*2;j<100;j+=i)
> {
> isprimes[i]= false;
> }
>
> }
> }
> int kindex=index;
>
> }
>
> /*
> But now , how should I find out the 1 millionth prime number ?
> It requires another seive , i know , but it requires still bigger
> range */
> Can you give me a pseudocode ?
> */
>
> On Jan 26, 8:20 pm, juver++ wrote:
>
>
>
> > @above One million is 10^6.
> > Problem wants 1 million of prime numbers. Not the prime numbers in range
> > 1..1000.
> > So, you should use two sieves.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
Correct me if I'm wrong , but according to you , will this be the
approach ?
boolean array[10];
int primes[100];
void seive()
{
int index=0;
for(int i=2;i*i<10;i++)
{
if(isprime[i])
{
primes[index++]=i;
for(int j=i*2;j<100;j+=i)
{
isprimes[i]= false;
}
}
}
int kindex=index;
}
/*
But now , how should I find out the 1 millionth prime number ?
It requires another seive , i know , but it requires still bigger
range */
Can you give me a pseudocode ?
*/
On Jan 26, 8:20 pm, juver++ wrote:
> @above One million is 10^6.
> Problem wants 1 million of prime numbers. Not the prime numbers in range
> 1..1000.
> So, you should use two sieves.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
#include
#include
#include
#define MAX 15485863
#define LMT 100
unsigned flag[MAX>>6];
#define ifc(n) (flag[n>>6]&(1<<((n>>1)&31)))
#define isc(n) (flag[n>>6]|=(1<<((n>>1)&31)))
void sieve() {
unsigned i, j, k;
for(i=3; i>6);
}
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
@above One million is 10^6. Problem wants 1 million of prime numbers. Not the prime numbers in range 1..1000. So, you should use two sieves. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime Numbers
@rahul, juver++,sankalp Though this can be solved using incrementing the range in sieve. But due to this incremental approach how much the efficiency can be improved, any guesses :) -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
Use a seive . it's complexity is O(nlog n) 1 million is 1*10^7 , this will run within time limit ... assuming u optimize ur code enough !! On Jan 26, 5:48 pm, juver++ wrote: > Generate primes numbers for the range 1..10^7 using sieve. > Than apply sieve bigger range using these prime numbers. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime Numbers
Generate primes numbers for the range 1..10^7 using sieve. Than apply sieve bigger range using these prime numbers. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime Numbers
I think one can use an elimination method . List out all the numbers
. Keep on eliminating the multiples of 2{excluding 2} , then multiples
of 3 , then multiples of 5 , then 7 , the denseness of the numbers
eliminated will get less . And obviouslly you will get the numbers .
On 1/25/11, siddharth srivastava wrote:
> Hey Dave
>
> On 25 January 2011 18:17, Dave wrote:
>
>> The most efficient approach is to google "millionth prime number" and
>> select the first hit.
>>
>> Good one. But it was asked to me in an interview.
> The trivial approach would be to check for every number to be a prime an
> continue till
> the count of prime no reaches 1 million.
>
> Another approach according to me would be to use gcd approach for the same
> but it doesn't guarantees the order of primes I guess (correct me if I am
> wrong)
>
> The interviewer still wanted a better approach. I know of better approaches
> if a range is given, but what to do in this case.
>
>
>> Dave
>>
>> On Jan 25, 6:00 am, siddharth srivastava wrote:
>> > Hi
>> >
>> > Its an easy one but still I am looking for the most efficient approach.
>> >
>> > Find first 1 million prime numbers.
>> >
>> > --
>> > Siddharth Srivastava
>> >
>> > When you have learned to snatch the error code from the trap frame, it
>> will
>> > be time for you to leave.
>>
>> --
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>> To post to this group, send email to algogeeks@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.
>>
>>
>
>
> --
> Siddharth Srivastava
>
> When you have learned to snatch the error code from the trap frame, it will
> be time for you to leave.
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algogeeks@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.
>
>
--
Rahul K Rai
rahulpossi...@gmail.com
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@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.
Re: [algogeeks] Re: Prime Numbers
Hey Dave On 25 January 2011 18:17, Dave wrote: > The most efficient approach is to google "millionth prime number" and > select the first hit. > > Good one. But it was asked to me in an interview. The trivial approach would be to check for every number to be a prime an continue till the count of prime no reaches 1 million. Another approach according to me would be to use gcd approach for the same but it doesn't guarantees the order of primes I guess (correct me if I am wrong) The interviewer still wanted a better approach. I know of better approaches if a range is given, but what to do in this case. > Dave > > On Jan 25, 6:00 am, siddharth srivastava wrote: > > Hi > > > > Its an easy one but still I am looking for the most efficient approach. > > > > Find first 1 million prime numbers. > > > > -- > > Siddharth Srivastava > > > > When you have learned to snatch the error code from the trap frame, it > will > > be time for you to leave. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@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. > > -- Siddharth Srivastava When you have learned to snatch the error code from the trap frame, it will be time for you to leave. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
[algogeeks] Re: Prime Numbers
The most efficient approach is to google "millionth prime number" and select the first hit. Dave On Jan 25, 6:00 am, siddharth srivastava wrote: > Hi > > Its an easy one but still I am looking for the most efficient approach. > > Find first 1 million prime numbers. > > -- > Siddharth Srivastava > > When you have learned to snatch the error code from the trap frame, it will > be time for you to leave. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@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.
