Tushar Goel

Ranch Hand

Posts: 934

4

posted 2 years ago

Hi All, i am working on an assignment given by my professor where i have to give the solution in square root complexity but i am unable to understand how to get it? I looked on the google but din't understand.

Could any one please give me an example and explain how to get square root complexity?

Could any one please give me an example and explain how to get square root complexity?

Piet Souris

Master Rancher

Posts: 2044

75

Tushar Goel

Ranch Hand

Posts: 934

4

posted 2 years ago

Thanks Jasper.. You mean like if i have numbers 0 to 100 and square root of 100 is 10 then i have to find numbers having space 10. ex: 0, 10, 20, 30,... 100?

Thanks Piet.. Are you referring the same condition as i mentioned above?

Could you please guys share some link or example where i can see the implementation ?

Thanks Piet.. Are you referring the same condition as i mentioned above?

Could you please guys share some link or example where i can see the implementation ?

Campbell Ritchie

Marshal

Posts: 56553

172

posted 2 years ago

Surely that is the Sieve of Eratosthenes.

No, for 100 you would test up to √100 using 2, 3, 4, 5, 6, 7, 8, 9, 10.

It says in

In Abelson and Sussman it mentions a simpler method of finding whether a number is prime which runs in constant time but may miss out some values. So,1: Populating a sieve runs in 2: Using a ready‑made sieve to find whether a number is prime runs in logarithmic time. 3: Testing for primeness without a sieve runs in √

No, for 100 you would test up to √100 using 2, 3, 4, 5, 6, 7, 8, 9, 10.

It says in

*the Curious Incident of the Dog in the Night‑Time*that the number of prime numbers up to a certain number*n*is approximately proportional to log*n*. If you already have a source of prime numbers in order, then you would need to check up to*i*log(√*n*) numbers (*i*being an unspecified integer). But log(√*n*) = ½log(*n*), so that reduces to logarithmic complexity.In Abelson and Sussman it mentions a simpler method of finding whether a number is prime which runs in constant time but may miss out some values. So,

*n*log

*n*time.

*n*time at worst. Somebody may be able to show it is quicker. Since most factors are small (2, 3, 5 etc) it may actually run in logarithmic time. Not sure, however.

Piet Souris

Master Rancher

Posts: 2044

75

posted 2 years ago

?

I gave OP an example of something that looks like O(sqrt(n)). That's what OP asked for.

Now, indeed I'm not sure if my example is indeed a sqrt(n), but it's just an example.

What the sieve of Eratosthenes has to do with that is beyond me.

Campbell Ritchie wrote:Surely that is the Sieve of Eratosthenes. (...)

?

I gave OP an example of something that looks like O(sqrt(n)). That's what OP asked for.

Now, indeed I'm not sure if my example is indeed a sqrt(n), but it's just an example.

What the sieve of Eratosthenes has to do with that is beyond me.

Tushar Goel

Ranch Hand

Posts: 934

4

posted 2 years ago

Campbell, I am still trying to understand what you said. They still floating over my head.

I think you are referring to this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

I think you are referring to this: http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

Campbell Ritchie

Marshal

Posts: 56553

172

Ivan Jozsef Balazs

Rancher

Posts: 999

5

posted 2 years ago

It has not that fancy title but it says here:

Prime number theorem

that

and here Prime-counting function

that

Campbell Ritchie wrote:

It says inthe Curious Incident of the Dog in the Night‑Timethat the number of prime numbers up to a certain numbernis approximately proportional to logn.

It has not that fancy title but it says here:

Prime number theorem

that

The first such distribution found is π(N) ~ N / ln(N), where π(N) is the prime-counting function and ln(N) is the natural logarithm of N.

and here Prime-counting function

that

In mathematics, the prime-counting function is the function counting the number of prime numbers less than or equal to some real number x

Campbell Ritchie

Marshal

Posts: 56553

172

Ivan Jozsef Balazs

Rancher

Posts: 999

5