### Codebank: Finding nth prime

Not the fastest but an elegant code written by me.

 ``1234567891011121314151617181920`` ``````// This code was written by Mert Ener #include #include // Requires a run button on Windows form. private: System::Void button1_Click_1(System::Object^ sender, System::EventArgs^ e) { UInt64 cloc = clock(); long o, m = 1; long k = long::Parse(textBox1->Text)-2; // The textbox you entered for the nth prime. vector p(1,2); for( long n = 0; n <= k; n++ ) { m += 2; for( long l = 1;o=p[l],o*o<=m; l++ ) { if (m % p[l] == 0) { m += 2; l=0;}} p.push_back(m);} textBox2->Text = p[k+1].ToString(); // The textbox for the result. MessageBox::Show("It took me " + (clock() - cloc).ToString() + " milliseconds to find your prime.");}``````
Last edited on
Got an error on line 6 when I compile. This looks a bit like Java
 This looks a bit like Java

Looks like C++\CLI - Microsoft's managed version of C++.

Although I don't think line 6 would compile anyway.
Last edited on
Oh sorry, my bad. That's right
 Looks like C++\CLI - Microsoft's managed version of C++.

It is a code written with VS2012 in C++.Net. It is for a windows userform with two textboxes and line 6 represents a click to run button.
The core of the code is here
 ``1234567891011`` ``````long o,m = 1; long k = "nth prime you like"; vector p(1,2); for( long n = 0; n <= k; n++ ) { m += 2; for( long l = 1;o=p[l],o*o<=m; l++ ) { if (m % p[l] == 0) { m += 2; l=0;}} p.push_back(m);} "The result is" = p[k+1]``````

and you may modify it as you like.
Last edited on
Yeah, your code also looks cool! In the forums, it has been said 4 sec. is a optimistic result for 1000000th prime. My code finds in less than 2 seconds on an ordinary pc.
Last edited on
I get floating point exception when I run yours
Yeah, can be. No problem. The code changed a bit also. I'll update in a free time.
Finally, it is a shortened and stable version of my original code.

 ``12345678`` ``````int k = "the nth prime you like" -1; int l,m=1,n,o; int*p;p=new int [k+1],p[0]=2; for(n=1;m+=2,n<=k;p[n]=m,n+=1) for(l=1,o=3;o*o<=m;(m%o==0)?(m+=2,l=1,o=3):(l+=1,o=p[l])); "the result" = p[k]``````

In fact the exact expression of my original code is this below. Even it is a shorter and slightly faster way,
 ``12345678`` ``````int k = "the nth prime you like" -1; int l,m=1,n,o; int*p;p=new int [k+1],p[0]=2; for(n=1;m+=2,n<=k;p[n]=m,n++) for(l=1;o=p[l],o*o<=m;(m%o==0)?(m+=2,l=1):(l++)); "the result" = p[k]``````

however it is unstable because of memory initialization issues and I couldn't overcome it. After 1000000th query it is giving division-by-zero error. Sometimes o gets 0 value even there is nothing such as 0 in array p. I can prove it because it runs so well around 1000000th queries. And m%0 causes the error. That's why I had to secure o many times in the first code. If someone can handle it, will be my welcome.
But the first code runs perfectly for 10000000th query around 40 seconds on an ordinary pc.
Last edited on
 ``12345678910111213141516171819202122232425262728293031323334`` ``````#include #include #include #include #include #include int main() { constexpr std::size_t n = 10000000 ; // use the prime number theorem to get an upper bound on the nth prime const auto logn = std::log(n) ; const std::size_t SZ = n * ( logn + std::log(logn) ) + 1 ; assert( SZ < std::numeric_limits::max() ) ; // generate a prime number sieve upto the upper_bound std::vector sieve( SZ, true ) ; const std::size_t RP1 = std::sqrt(SZ) + 2 ; for( std::size_t i = 2 ; i < RP1 ; ++i ) if( sieve[i] ) for( std::size_t j = i+i ; j < SZ ; j += i ) sieve[j] = false ; // and count till the nth prime number std::size_t cnt = 0 ; for( std::size_t i = 2 ; i < SZ ; ++i ) if( sieve[i] ) { ++cnt ; if( cnt == n ) { std::cout << "the " << n << "th prime number is " << i << '\n' ; break ; } } }``````

http://liveworkspace.org/code/1Ti4nB\$1

 ``12`` `````` constexpr std::size_t n = 10000000 ; ``````

constexpr: unidentified,
size_t: cannot be defined in current scope,
n: expected (;)
errors.
Last edited on
You need a compiler that supports C++11, the latest standard of C++ that was released in 2011.

Branflakes91093 wrote:
Looks like C++\CLI - Microsoft's managed version of C++.
Just like with Windows, they actually use a forward slash and not a backslash.
Wowww, It is amazing! I didn't know about that "Sieve of Eratosthenes" therorem. It works around10 times faster than my code! Amsome ;) It has some logarithmic expressions. I'll inspect this.
Last edited on
> I didn't know about that "Sieve of Eratosthenes" therorem.

The theorem is called the "prime number theorem"
http://en.wikipedia.org/wiki/Prime_number_theorem

The algorithm used for generating prime numbers is the "sieve of Eratosthenes"; the oldest and also the simplest sieve algorithm.
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Topic archived. No new replies allowed.