A community for technology geeks in Lebanon.

You are not logged in.

- Topics: Active • Unanswered

Pages: **1**

**Joe****Member**

Simple: What's the 10001st prime number?

**arithma****Member**

Now you're being just mean.

**Joe****Member**

I just spent two hours on it. One of the funnest exercises I've done in a while.

**Kareem****Member**

104743

*Last edited by Kareem (October 9 2010)*

**EddieEC****Member**

104743?

Edit: Just saw Kareem's post.

*Last edited by EddieEC (October 9 2010)*

**Joe****Member**

Anyone can Google, show me code!

**Kareem****Member**

```
#include <iostream>
#include <math.h>
#include <conio.h>
using namespace std;
bool isprime(unsigned long long int n)
{
for(unsigned long long int i=2;(i<=sqrt(n));i++)
if(n%i==0)
return false;
return true;
}
int main()
{
unsigned long long int i=1,count=1;
while(count<10001)
{
i+=2;
if(isprime(i)==true)
count ++;
}
printf("\n%d",i);
getch();
return i;
}
```

**mesa177****Member**

Code written in Matlab:

```
i = 2;
cnt = 0;
while(cnt ~= 10001)
if isprime(i)
cnt = cnt + 1;
end
i = i + 1;
end
disp(strcat('The 10001st prime number is:',num2str(i-1)));
```

Answer:

The 10001st prime number is:104743

*Last edited by mesa177 (October 9 2010)*

**mesa177****Member**

This is in C++

```
#include <iostream>
#include <conio.h>
#include <math.h>
bool isPrime (int num) // Original function courtesy Grey Wolf
{
if (num <=1)
return false;
else if (num == 2)
return true;
else if (num % 2 == 0)
return false;
else
{
bool prime = true;
int divisor = 3;
double num_d = static_cast<double>(num);
int upperLimit = static_cast<int>(sqrt(num_d) +1);
while (divisor <= upperLimit)
{
if (num % divisor == 0)
prime = false;
divisor +=2;
}
return prime;
}
}
void main(){
int i = 2, cnt = 0;
while (cnt != 10001){
if (isPrime(i))
cnt++;
i++;
}
cout << "The 10001st prime number is: " << (i-1) << endl;
getch();
}
```

*Last edited by mesa177 (October 9 2010)*

**Hybrid****Member**

This is in Java :)

```
public class Main
{
public static void main(String[] args)
{
final int target = 10001;
long num = 2;
int count = 0;
boolean isPrime = true;
while(true)
{
isPrime = true;
for(int i = 2; i < num; i++)
{
if(num%i==0)
{
isPrime = false;
break;
}
}
if(isPrime == true)
{
count++;
}
if (count == target)
{
break;
}
else
{
num++;
}
}
System.out.println("The 10001st prime number is: " + num);
}
}
```

**Output:** The 10001st prime number is: 104743

*Last edited by Hybrid (October 9 2010)*

**Joe****Member**

```
#include <stdio.h>
#include <stdlib.h>
#define NUMBER 1000000
int main (int argc, char** argv)
{
int numbers[NUMBER];
int i=0, prime=0, count=0, val=0;
for (i=0; i<NUMBER-1; i++)
{
numbers[i] = i+2; /* Array starts at 2. No need to test 0 or 1. */
}
for (i=0; i<NUMBER-1; i++)
{
if (numbers[i])
{
printf ("%d:\t%d\n", ++val, numbers[i]);
prime=numbers[i];
count=2;
while (count*prime-2<NUMBER-1)
{
numbers[count*prime-2]=0;
count++;
}
}
}
return 0;
}
```

using Eratosthene's Sieve to output all the prime between 2 and 1000001. Written in C, compiled with gcc. I find it to be a lot better than calculating isPrime for each number.

@mesa: your isPrime() function is very nicely written. ^^

**Georges****Member**

Adding to the same topic, i was asked today in the Information Security course to work with some prime numbers in order to develop an encryption algorithm...

One of the questions was to find the **nearest prime number** to a given number (which was a bit easier than i thought), but the real challenge is to find the **Primitive Roots** of that prime number...

If anyone has the enough curiosity to work on this too and post some results here i'd really appreciate it. And this is not a homework, so do not bother yourself replying by "We don't do your homeworks"...

Cheers folks'

**jibbo****Member**

Javascript

[edit] any idea on why the code apears messy ?

```
function isPrime(n) {
var sqr = Math.floor(Math.sqrt(n)+1);
var i = 3;
if (n<4){return true;}
if(n%2 === 0) { return false; }
while (i<sqr) {
if(n%i === 0) {return false; }
i += 2;
}
return true;
}
function listPrime(s){
var lastPrime, i=3, v=1;
while (v < s){
if(isPrime(i) === true){
lastPrime = i;
v++; i++;
} else {
i++;
}
}
return lastPrime;
}
listPrime(10001);
```

*Last edited by jibbo (September 30 2012)*

**Joe****Member**

any idea on why the code apears messy ?

It's because of tab indentation.

Ever since the move to the new LG version, we've been facing problems with tabs indentation.

In the meantime, you could set your text editor to use spaces instead.

I took the liberty to replace tabs by 4 spaces in the code you posted, in order to fix the "messiness".

**Ayman****Member**

And old thread but thought I'd contribute my C# solution I had some time ago. The isPrime function is simple yet effective in the sense that if a number x is divisible by any number that is between 2 and its square root inclusive then it is definitely a composite number if not then it should be prime.

```
static void Main(string[] args)
{
int target = 10001;
int countPrime = 0;
int primeNum = 2;
do
{
if (isPrime(primeNum))
Console.WriteLine(String.Format("{0} is the {1}",primeNum,++countPrime));
primeNum++;
} while (countPrime < target);
Console.Read();
}
public static bool isPrime(int x)
{
if (x == 2) return true;
for (int i = 2; i <= ((int)Math.Sqrt(x) + 1); i++)
if (x % i == 0) return false;
return true;
}
```

**kamilhanna1****Member**

considering 1 as a prime number it is

its 104729 , otherwise 104743

Code (BASIC) :

```
Public Class Form1
Private Sub Button1_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button1.Click
ListBox1.Items.Add(1)
Timer1.Start()
End Sub
Dim x As Integer = 2
Dim y As Integer = 1
Dim count As Integer = 1
Dim div As Integer = 0
Dim sum As ULong = 1
Private Sub Timer1_Tick(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Timer1.Tick
Do Until y = x + 1
If (x Mod y) = 0 Then div = div + 1
y = y + 1
Loop
If div = 2 Then ListBox1.Items.Add(x)
If div = 2 Then sum = sum + x
Label1.Text = "Sum=" & sum
If div = 2 Then count = count + 1
If count = TextBox1.Text Then Timer1.Stop()
x = x + 1
y = 1
div = 0
End Sub
Private Sub Button2_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles Button2.Click
Timer1.Stop()
ListBox1.Items.Clear()
x = 2
y = 1
count = 1
div = 0
Label1.Text = "Sum=0"
sum = 1
End Sub
Private Sub Button3_Click(ByVal sender As System.Object, ByVal e As System.EventArgs)
Close()
End Sub
```

*Last edited by kamilhanna1 (January 6 2013)*

**CodingFreak****Member**

kamilhanna1 wrote:

considering 1 as a prime number

I remember reading that 1 is neither prime or composite

Answer in C++:

```
#include <iostream>
#include <cmath>
using namespace std;
int main() {
int counter = 0;
int i;
for (i = 2; counter != 10001; i++) {
bool is_prime = true;
for (int j = 2; j <= sqrt(i); j++) {
if (i%j == 0) {
is_prime = false;
break;
}
}
if (is_prime) {
cout << i << endl;
counter++;
}
}
}
```

*Last edited by CodingFreak (January 7 2013)*

**mmk92****Member**

I see everyone approached it with a different logic, what I noticed is that you guys didn't consider excluding even numbers.

Here's my code:

```
public class PrimeNumbers
{
public static void main(String[] args)
{
int primeCount = 2;
int currentNbr = 1;
while(primeCount<=10001)
{
currentNbr = currentNbr + 2;
if(isPrimeNumber(currentNbr))
{
primeCount++;
}
}
System.out.print(currentNbr);
}
public static boolean isPrimeNumber(int n)
{
int multiples = n;
for(int i = 3; i<=(Math.sqrt(n)); i = i + 2)
{
if(n%i == 0)
{
multiples = multiples*i;
}
}
if(multiples == n)
{
return true;
}
else
{
return false;
}
}
}
```

If you exclude even numbers the code will run MUCH faster, because as everyone SHOULD know all even nbrs are devisible by atleast themselves, 2, and 1), and I used the rule that no number has a divisor bigger then the square root of itself to significantly reduce the time it takes to finish the for loop in the second method.

These little steps go a LONG way when your dealing with ie the 10000001th prime number, it significantly cuts the time for the code to completely finish.

*Last edited by mmk92 (January 8 2013)*

**Joe****Member**

@mmk92: Props on realizing that you can improve execution time.

A small misconception though: As counter intuitive as it may seem, halving the number of steps is not a **huge** improvement over the original one. As a matter of facts, by canceling the even numbers, you're only taking out a small fraction of the necessary steps (since determining the primality of an even number is a **very** fast computation. It's only one step!).

Scientists have a way of measuring the complexity of an algorithm. And they do this by approximations, it's not an exact science.

According to this theory, multiplying (or dividing) this complexity by a constant factor, is always a void operation. For instance, if the complexity of execution of your code is a variable called O(X), then by definition it's also equivalent to O(X/2).

I did write a blog post a few months ago about testing very large numbers for primality. You should take a look.

**mmk92****Member**

rahmu wrote:

@mmk92: Props on realizing that you can improve execution time.

A small misconception though: As counter intuitive as it may seem, halving the number of steps is not a

hugeimprovement over the original one. As a matter of facts, by canceling the even numbers, you're only taking out a small fraction of the necessary steps (since determining the primality of an even number is averyfast computation. It's only one step!).Scientists have a way of measuring the complexity of an algorithm. And they do this by approximations, it's not an exact science.

According to this theory, multiplying (or dividing) this complexity by a constant factor, is always a void operation. For instance, if the complexity of execution of your code is a variable called O(X), then by definition it's also equivalent to O(X/2).

I did write a blog post a few months ago about testing very large numbers for primality. You should take a look.

I am familiar with time complexity, but if you notice I applied the same logic on the loop in the isPrimeNumber method(since the number isn't even, all even numbers are disregarded). So it takes a further step into decreasing the time of execution

**NuclearVision****Member**

```
//primes
#include <iostream>
#include <math.h>
using namespace std;
bool isprime(int n)
{ int lim=sqrt(n)+1;
if (n==2) return true;
if (n<2) return false;
for (int i=2;i<lim; i++)
{if (n%i==0) return false;
}
return true;
}
int main()
{ int j=1,e=1;//j=1 because 2 will not be count in the loop
while (true)
{ e+=2;// one of 2 consecutive numbers ==0 mod 2
if (isprime(e)==1) j++;
if (j==10001)
{
cout<<e<<endl;
break;
}
}
return 0;
}
```

**NuclearVision****Member**

```
def isprime(n):
if n==2: return True
if n==1 or n%2==0: return False
if [i for i in xrange(2,int(n**(0.5)+1)) if n%i==0]==[]: return True
return False
n,z=0,0
while not z==10001:
n+=1
if isprime(n) is True: z+=1
print n
```

Pages: **1**