[Exercise] Prime numbers

Joe

Simple: What's the 10001st prime number?

arithma

Now you're being just mean.

Joe

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

Kareem

104743

EddieEC

104743?

Edit: Just saw Kareem's post.

Joe

Anyone can Google, show me code!

Kareem

#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

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

mesa177

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

Hybrid

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

Joe

#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

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

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

Joe

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

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

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

CodingFreak

kamilhanna1 wroteconsidering 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++;
                }
        }
}

mmk92

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.

Joe

@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

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