• Coding

  • [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'
2 years later
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);
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".
a month later
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;
        }
2 months later
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
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++;
                }
        }
}
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.
@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.
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
a year later
//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;
}
a year later
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