Hi,

the IBM Ponder this Challenge from August 2018 http://www.research.ibm.com/haifa/ponderthis/challenges/August2018.html dealt with prime numbers and I realized not much has been written yet about prime numbers and OPL. Plus I ve read recently that in the 10 most important algorithms anyone should know we hve both https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and the simplex!

So let me share this.

    int m=1000000;
    range r=1..m;
    int prime[i in r]=(i!=1) &&and(j in 2..ftoi(ceil(sqrt(i-1)))) (0!=i mod j); // is prime ?

    // One by one
    {int} primes={i | i in r : 1==prime[i]};

    execute
    {
    primes;
    }

    {int} nonPrimes;

    // Eratosthenes
    execute
    {
    for(var i in r) if (i!=1)
     if (!nonPrimes.contains(i))
        {
          j=2*i;
          while (j<=m)
          {
            nonPrimes.add(j);
            j=j+i;      
          }    
        }

    }

    {int} primes2=asSet(r) diff nonPrimes diff {1};

    execute
    {
    primes2;
    }

    assert card(primes)==card(primes2);
    assert card(primes symdiff primes2)==0;

which computes the prime numbers til n. (2 methods)

Which leads to 2 models if we want to maximize x+y such as x and y are prime and x+y<=n

using CP;

int n=1000000;

range r=1..n;

dvar int x in r;
dvar int y in r;

maximize x+y;
subject to
{
x+y<=n;

(x==1) || and(j in 2..ftoi(ceil(sqrt(n-1)))) (0!=x mod j);
(y==1) || and(j in 2..ftoi(ceil(sqrt(n-1)))) (0!=y mod j);
}

and

using CP;

int n=1000000;
range r=1..n;
int prime[i in r]=(i==1) || and(j in 2..ftoi(ceil(sqrt(i-1)))) (0!=i mod j); // is prime ?

{int} primes={i | i in r : 1==prime[i]};

 

dvar int x in r;
dvar int y in r;

maximize x+y;
subject to
{
x+y<=n;

x in primes;
y in primes;
}

regards