LUA PRIME CALCULATOR using preprocessing based on Sieve of Eratosthenes

This article shows a lua script to calculate an ordered prime list starting with 2, 3, 5, 7, etc.


We are going to improve former lua prime calculator using a preprocessing table.
This table will allow us to discard quickly some numbers and its multiples.

Within this lua script, first we perform some preprocessing, and after that actual prime testing for remaining numbers are performed.

Sieve of Eratosthenes

Sieve of Eratosthenes is an algorithm to calculate a prime number list up to a chosen number.

In this program we will use this algorithm to generate a preprocessing table.


Some examples are useful to show how preprocessing table works:

Tables are generated using a sequence with first prime numbers.

E.g:

Preprocessing table for 2

{2}

So we will test numbers this way:
We start with number one, and sum to it the first number from preprocessing table:
1+2 = 3 (3 is the next number to test for primality)

Once preprocessing table has completed, we start from first element again (2):
3+2 = 5

5+2 = 7

Read more »

Calculate a PRIME number LIST using C language

This C program calculates a list with first prime numbers.

Build the program

C is a compiled language, so we will need to install a C compiler: gcc
$ sudo aptitude install gcc

We copy this text in a file, e.g: prime_calculator.c

Next we compile the file:
$ gcc -o prime_calculator -lm prime_calculator.c -Wall

or if we want further optimization:
$ gcc -o prime_calculator -lm prime_calculator.c -Wall -O3

-lm option links the math library so we can calculate square roots.

Execute the program

After compilation, an executable appears: prime_calculator.
$ chmod a+x prime_calculator # we grant it execution permission.

If we want to show first ten prime numbers:
$ ./prime_calculator 10
PRIME LIST:
2 3 5 7 11 13 17 19 23 29

If we pass more than two arguments, it calculates the prime list but does not show anything. Just to measure its execution time:
$ time ./prime_calculator 10 *
real 0m0.008s
user 0m0.004s
sys 0m0.000s

Read more »

Lua: Calculate a prime number list

Lua is an extension language.


This script calculates a prime number list starting with smaller ones.


To run this script you need to install lua language: (e.g: in Debian or Ubuntu)
$ sudo aptitude install lua

Current version(when this article was written) is 5.1:
$ sudo aptitude install lua5.1


After installing it, lua interpreter could be found in /usr/bin/lua.

Then you copy this script in a file, e.g: primes.lua and exec:

$ lua primes.lua 20 # it will calculate first twenty prime numbers.

or give execution permissions to the file:
$ chmod a+x primes.lua
$ ./primes.lua 20

Read more »

Calculate Prime Numbers using an ARDUINO Board

Following example uses an Arduino board to calculate a prime number list, starting from one.
It shows the result using serial port communication.

BUILDING AND RUNNING THE CODE

You should copy this code into your Arduino IDE window, compile it (C-R), upload the code into the board (C-U) and to see the result open the serial monitor (C-Shift-M).

If everything goes fine your serial monitor will show a prime on each line every time it is calculated. Maximum prime able to be calculated depends on long type maximum value.

long number = 3;

void setup()
{
  Serial.begin(9600);
  Serial.println("#");
  Serial.println("1");
  Serial.println("2");
}

void loop()
{
  int is_prime = 1;
  long i = 3;
  long top = sqrt(number);
  while (i<top)
  {
    if (number%i == 0)
    {
      is_prime = 0;
      break;
    }
    i++;
  }
  if (is_prime)
  {
    Serial.println(number,DEC);
  }
  number += 2;
}

Within setup function, it shows 1 and 2 primes. It then starts calculating in the main loop using number 3.

Primality test here consists on performing divisions and checking the remainder. It is not needed to test with every divisor, when square root is reached we know it is a prime.

When a prime number is found it is sent over serial line.

As we start calculations with number three, we can skip all even numbers.

YOU MAY ALSO BE INTERESTED IN:

Install and run a program in Arduino using 64 bits Ubuntu (lucid) distro

Calculate prime numbers using PHP

Simply create a file named primeNumberCalculator.php. Copy following text in it.

You need a web server supporting php scripting.
Place the file where your http web server see it. e.g: /var/www

Open the file in a web browser. e.g: http://localhost/primeNumberCalculator.php

<html>
<body>

<h2>PHP Prime number calculator</h2>
<form name="input" action="primeNumberCalculator.php" method="get">
How many primes?: <input type="text" name="count" />
<input type="submit" value="Submit" />
</form>
<?php

// How many prime numbers are we going to calculate:
$count=$_GET["count"];
if ($count == "") {
   $count = 10;  // Default value
}

// We show the first prime number:
$prime_array=array("2");
echo $prime_array[0];
echo " ";

$total=1; // prime number array length.
$number = 3; // current number we are going to test for primality.

$i=1; // We start with 1 because first prime is already printed.
while ( $i<$count ) {
   $index=0;
   $is_prime="true";
   $max = floor(sqrt($number));
   $n = $prime_array[$index];
   while(($n <= $max) && ($is_prime == "true")) {
      if (($number % $n) == 0) {
         $is_prime="false";
      }
      $index++;
      $n = $prime_array[$index];
   }
   if ($is_prime=="true") {
      echo " " . $number;
      $prime_array[$total] = $number;
      $total++;
      $i++;
   }

   $number += 2;
}

?>

</body>
</html>

Calculate a PRIME NUMBER list using JAVA

This article shows how to write, compile, build and execute a program that calculates a list containing the first prime numbers using Java language.

We are going to create a source code file named CalculatePrimeNumbers.java
Then we copy/paste next programm in that file.

NOTE: Name is important, because in Java language file name has to match the class it contains.

import java.util.ArrayList;

/**
 * Description of CalculatePrimeNumbers class.
 */
public class CalculatePrimeNumbers {

    // By default it shows 50 first prime numbers.
    private static final int MAX_PRIMES = 50;


    /**
     * @param args the command line arguments
     * This function accepts zero or one arguments.
     * When called with no arguments it shows 50 first prime numbers.
     * If we specify a number, it shows that a prime number array with that specified length.
     */
    public static void main(String[] args) {
        int top;

 // Parse command line arguments.
        switch(args.length){
            case 0:
                top = MAX_PRIMES;
                break;
            case 1:
                top = Integer.parseInt(args[0]);
                break;
            default:
                System.err.println("ERROR: TOO MANY ARGUMENTS.");
                return;
        }
        System.out.println("We are going to calculate " + top + " first prime numbers.");


 ArrayList<long> primes = new ArrayList<long>();
        primes.add(2L); // 2 is the first prime number we get.
 long index = 3; // Calculations start for number 3.

        System.out.println("Prime number list:");
        System.out.print(2 + " ");
        while (primes.size() < top) {
            boolean isPrime = true;

     for(long n:primes) {
                if ((index % n) == 0) {
                    isPrime = false;
                    break;
                }
            } // End for.

            if (isPrime) {
                // index stores a prime number.
                primes.add(index);
                System.out.print(index + " ");
            }

            index++;
        } // End while.
       
    } // End main.

}

Java is a programming language that is compiled into bytecodes.

Read more »

Calculating Prime Numbers using python

This blog article shows a python exercise which consists on calculating some prime numbers using trial division algorithm.

You can copy this code in a script file and then execute it!

#!/usr/bin/env python

#Prime numbers
import sys
import math

print "Prime numbers"

#Asks user how many numbers he wants to calculate.
top = int(raw_input("How many prime numbers do you want to calculate?: "))

if (top <1 ) :
print "Error: Invalid number. It must be greater than one"
sys.exit

#Initializing some variables
a = 3    # first number to test if it is prime.
result = [2]  # result list begins with prime number 2.
num = 1   # number of already calculated primes.
print 2,

while num < top : # main loop
cont = 0

# Performs the division test
while 1 :
divisor = result[cont]   # we only test with already calculated prime numbers.

(quotient, remainder) = divmod(a,divisor)  # calculates quotient and remainder at the same time.

if (remainder) :
if divisor <= quotient :
cont += 1 
else:
result.append(a)
print a,  # number a is a prime.
num += 1
break
else:
break   # number a is not a prime

a += 1   # calculate next number to test.

This other script avoids testing numbers that are multiple of 2,3,5 or 7. Also calculates the integer square root to obtain the higher divisor limit to test for each number.

#!/usr/bin/env python

#Prime numbers
import sys
import math

print "Prime numbers"

#Asks user how many numbers he wants to calculate.
top = int(raw_input("How many prime numbers do you want to calculate?: "))

if (top <1 ) :
print "Error: Invalid number. It must be greater than one"
sys.exit

#Initializing some variables
a = 11   # first number to test if it is prime
statea = 0
stateb = 0
result = [7]  # result list begins with prime number 7
num = 4   # number of already calculated primes.
print 2, 3, 5, 7,

while num < top : # main loop
cont = 0

#Calculates the integer square root of a
low = 1
upper = a
while (upper - low) > 1 :
med = (low + upper)/2
temp = med * med
if temp > a :
upper = med
else:
low = med
if temp == a :
break

# Performs the division test
while 1 :
divisor = result[cont]
if (a % divisor) :
if divisor <= low :
cont += 1
else:
result.append(a)
print a,  # number a is a prime
num += 1
break
else:
break   # number a is not a prime

# Calculates next number to test if it is a prime.
if (stateb == 4) or (stateb == 6) :
a += 6
stateb += 1
elif statea :
a += 4
statea = 0
if stateb == 7 :
stateb = 0
else :
stateb += 1
else :
a += 2
statea = 1
stateb +=1