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





primefct.mos

(!******************************************************
   Mosel User Guide Example Problems
   ================================= 

   file primefct.mos 
   `````````````````
   Working with sets. Function returning a set.
 
   (c) 2008 Fair Isaac Corporation
       author: S. Heipcke, Nov. 2005
*******************************************************!)

model "Prime (fct)"
 parameters
  LIMIT=100                     ! Search for prime numbers in 2..LIMIT
 end-parameters

 forward function calc_prime(l: integer): set of integer

 declarations
  P: set of integer             ! Set of prime numbers
 end-declarations
 
 writeln("Prime numbers between 2 and ", LIMIT, ":")

 P:= calc_prime(LIMIT)          ! Calculate prime numbers

 writeln(P)
 writeln(" (", getsize(P), " prime numbers.)")


!*****************************************************************

 function calc_prime(l: integer): set of integer
  declarations
   SNumbers: set of integer     ! Set of numbers to be checked
   SPrime: set of integer       ! Set of prime numbers
  end-declarations

  SNumbers:={2..LIMIT} 

  n:=2
  repeat
    while (not(n in SNumbers)) n+=1
    SPrime += {n}               ! n is a prime number
    i:=n
    while (i<=LIMIT) do         ! Remove n and all its multiples
      SNumbers-= {i}
      i+=n
    end-do
  until SNumbers={}    
  returned:= SPrime
 end-function
 
end-model

Back to examples browserPrevious exampleNext example