LebGeeks

A community for technology geeks in Lebanon.

You are not logged in.

#1 October 9 2010

Joe
Member

[Exercise] Prime numbers

Simple: What's the 10001st prime number?

Offline

#2 October 9 2010

arithma
Member

Re: [Exercise] Prime numbers

Now you're being just mean.

Offline

#3 October 9 2010

Joe
Member

Re: [Exercise] Prime numbers

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

Offline

#4 October 9 2010

Kareem
Member

Re: [Exercise] Prime numbers

104743

Last edited by Kareem (October 9 2010)

Offline

#5 October 9 2010

EddieEC
Member

Re: [Exercise] Prime numbers

104743?

Edit: Just saw Kareem's post.

Last edited by EddieEC (October 9 2010)

Offline

#6 October 9 2010

Joe
Member

Re: [Exercise] Prime numbers

Anyone can Google, show me code!

Offline

#7 October 9 2010

Kareem
Member

Re: [Exercise] Prime numbers

#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;
                        }

Offline

#8 October 9 2010

mesa177
Member

Re: [Exercise] Prime numbers

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)

Offline

#9 October 9 2010

mesa177
Member

Re: [Exercise] Prime numbers

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)

Offline

#10 October 9 2010

Hybrid
Member

Re: [Exercise] Prime numbers

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)

Offline

#11 October 13 2010

Joe
Member

Re: [Exercise] Prime numbers

#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. ^^

Offline

#12 November 26 2010

Georges
Member

Re: [Exercise] Prime numbers

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'

Offline

#13 September 30 2012

jibbo
Member

Re: [Exercise] Prime numbers

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)

Offline

#14 September 30 2012

Joe
Member

Re: [Exercise] Prime numbers

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".

Offline

#15 November 4 2012

Ayman
Member

Re: [Exercise] Prime numbers

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;
        }

Offline

#16 January 6 2013

kamilhanna1
Member

Re: [Exercise] Prime numbers

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)

Offline

#17 January 7 2013

CodingFreak
Member

Re: [Exercise] Prime numbers

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)

Offline

#18 January 8 2013

mmk92
Member

Re: [Exercise] Prime numbers

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)

Offline

#19 January 8 2013

Joe
Member

Re: [Exercise] Prime numbers

@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.

Offline

#20 January 8 2013

mmk92
Member

Re: [Exercise] Prime numbers

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 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.

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

Offline

#21 April 18 2014

NuclearVision
Member

Re: [Exercise] Prime numbers

//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;
}   

Offline

#22 July 19 2015

NuclearVision
Member

Re: [Exercise] Prime numbers

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

Offline

Board footer