FICO Xpress Optimization Examples Repository
 FICO Optimization Community FICO Xpress Optimization Home

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
By clicking on a file name, a preview is opened at the bottom of this page.

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