Codebank: Finding nth prime

[Flashbond]

Not the fastest but an elegant code written by me.

// This code was written by Mert Ener
#include <time.h>
#include <iostream>

// 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<int> 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.");}

[Smac89]

Got an error on line 6 when I compile. This looks a bit like Java

[Branflakes91093]

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.

[Flashbond]

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

long o,m = 1;
long k = "nth prime you like";
vector<int> 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.

[Smac89]

Also been working on something like this:

http://villavu.com/forum/showthread.php?t=93657&p=1139885#post1139885

[Flashbond]

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.

[Smac89]

I get floating point exception when I run yours

[Flashbond]

Yeah, can be. No problem. The code changed a bit also. I'll update in a free time.

[Flashbond]

Finally, it is a shortened and stable version of my original code.

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,

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.

[JLBorges]

#include <iostream>
#include <cmath>
#include <cassert>
#include <limits>
#include <cstdint>
#include <vector>

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<std::size_t>::max() ) ;

   // generate a prime number sieve upto the upper_bound
   std::vector<bool> 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

[Flashbond]

  constexpr std::size_t n = 10000000 ;
   

constexpr: unidentified,
size_t: cannot be defined in current scope,
n: expected (;)
errors.

[LB]

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.

[JLBorges]

C++98: http://liveworkspace.org/code/1Ti4nB$2

[Flashbond]

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.

[JLBorges]

> 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