FICO
FICO Xpress Optimization Examples Repository
FICO Optimization Community FICO Xpress Optimization Home
Back to examples browserPrevious exampleNext example

Prime numbers using the Sieve of Eratosthenes

Description
This example calculat all prime numbers between 2 and a given upper bound shows the following features:
  • working with sets
  • nested loops: repeat-until, while, while-do
Algorithm 'Sieve of Eratosthenes': Starting with the smallest one, the algorithm takes every element of a set of numbers SNumbers (positive numbers between 2 and some upper limit that may be specified when running the model), adds it to the set of prime numbers SPrime and removes the number and all its multiples from the set SNumbers.

Further explanation of this example: 'Mosel User Guide', Section 8.3 Working with sets.


Source Files





prime.mos

(!*******************************************************
  * Mosel Example Problems                              *
  * ======================                              *
  *                                                     *
  * file prime.mos                                      *
  * ``````````````                                      *
  * Example for the use of the Mosel language           *
  * (Calculation of prime numbers)                      *
  *                                                     *
  * Implements the Sieve of Eratosthenes: each time a   *
  * prime number is found all of its multiples are      *
  * deleted from the set of remaining numbers.          *
  *                                                     *
  * (c) 2008 Fair Isaac Corporation                     *
  *     author: S. Heipcke, 2001                        *
  *******************************************************!)

model Prime                    ! Start a new model

parameters
 LIMIT=100                     ! Search for prime numbers in 2..LIMIT
end-parameters

declarations
 SNumbers: set of integer      ! Set of numbers to be checked
 SPrime: set of integer        ! Set of prime numbers
end-declarations

 SNumbers:={2..LIMIT} 
 
 writeln("Prime numbers between 2 and ", LIMIT, ":")

 n:=2
 repeat
   while (not(n in SNumbers)) n+=1
   SPrime += {n}
   i:=n
   while (i<=LIMIT) do
     SNumbers-= {i}
     i+=n
   end-do
 until SNumbers={}    

 writeln(SPrime)
 
end-model

Back to examples browserPrevious exampleNext example