Next special primes: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:23, 26 March 2021

Task

n is smallest prime such that the difference of successive terms is strictly increasing, where n < 1050.

C

<lang c>#include <stdio.h>

include <stdbool.h>

bool isPrime(int n) {

   int d;
   if (n < 2)  return false;
   if (!(n%2)) return n == 2;
   if (!(n%3)) return n == 3;
   d = 5;
   while (d*d <= n) {
       if (!(n%d)) return false;
       d += 2;
       if (!(n%d)) return false;
       d += 4;
   }
   return true;

}

int main() {

   int i, lastSpecial = 3, lastGap = 1;
   printf("Special primes under 1,050:\n");
   printf("Prime1 Prime2 Gap\n");
   printf("%6d %6d %3d\n", 2, 3, lastGap);
   for (i = 5; i < 1050; i += 2) {
       if (isPrime(i) && (i-lastSpecial) > lastGap) {
           lastGap = i - lastSpecial;
           printf("%6d %6d %3d\n", lastSpecial, i, lastGap);
           lastSpecial = i;
       }
   }

}</lang>

Output:

Special primes under 1,050:
Prime1 Prime2 Gap
     2      3   1
     3      5   2
     5     11   6
    11     19   8
    19     29  10
    29     41  12
    41     59  18
    59     79  20
    79    101  22
   101    127  26
   127    157  30
   157    191  34
   191    227  36
   227    269  42
   269    313  44
   313    359  46
   359    409  50
   409    461  52
   461    521  60
   521    587  66
   587    659  72
   659    733  74
   733    809  76
   809    887  78
   887    967  80
   967   1049  82

Go

<lang go>package main

import "fmt"

func sieve(limit int) []bool {

   limit++
   // True denotes composite, false denotes prime.
   c := make([]bool, limit) // all false by default
   c[0] = true
   c[1] = true
   // no need to bother with even numbers over 2 for this task
   p := 3 // Start from 3.
   for {
       p2 := p * p
       if p2 >= limit {
           break
       }
       for i := p2; i < limit; i += 2 * p {
           c[i] = true
       }
       for {
           p += 2
           if !c[p] {
               break
           }
       }
   }
   return c

}

func main() {

   c := sieve(1049)
   fmt.Println("Special primes under 1,050:")
   fmt.Println("Prime1 Prime2 Gap")
   lastSpecial := 3
   lastGap := 1
   fmt.Printf("%6d %6d %3d\n", 2, 3, lastGap)
   for i := 5; i < 1050; i += 2 {
       if !c[i] && (i-lastSpecial) > lastGap {
           lastGap = i - lastSpecial
           fmt.Printf("%6d %6d %3d\n", lastSpecial, i, lastGap)
           lastSpecial = i
       }
   }

}</lang>

Output:

Special primes under 1,050:
Prime1 Prime2 Gap
     2      3   1
     3      5   2
     5     11   6
    11     19   8
    19     29  10
    29     41  12
    41     59  18
    59     79  20
    79    101  22
   101    127  26
   127    157  30
   157    191  34
   191    227  36
   227    269  42
   269    313  44
   313    359  46
   359    409  50
   409    461  52
   461    521  60
   521    587  66
   587    659  72
   659    733  74
   733    809  76
   809    887  78
   887    967  80
   967   1049  82

Java

Translation of: C

<lang java>class SpecialPrimes {

   private static boolean isPrime(int n) {
       if (n < 2)  return false;
       if (n%2 == 0) return n == 2;
       if (n%3 == 0) return n == 3;
       int d = 5;
       while (d*d <= n) {
           if (n%d == 0) return false;
           d += 2;
           if (n%d == 0) return false;
           d += 4;
       }
       return true;
   }

   public static void main(String[] args) {
       System.out.println("Special primes under 1,050:");
       System.out.println("Prime1 Prime2 Gap");
       int lastSpecial = 3;
       int lastGap = 1;
       System.out.printf("%6d %6d %3d\n", 2, 3, lastGap);
       for (int i = 5; i < 1050; i += 2) {
           if (isPrime(i) && (i-lastSpecial) > lastGap) {
               lastGap = i - lastSpecial;
               System.out.printf("%6d %6d %3d\n", lastSpecial, i, lastGap);
               lastSpecial = i;
           }
       }
   }

}</lang>

Output:

Special primes under 1,050:
Prime1 Prime2 Gap
     2      3   1
     3      5   2
     5     11   6
    11     19   8
    19     29  10
    29     41  12
    41     59  18
    59     79  20
    79    101  22
   101    127  26
   127    157  30
   157    191  34
   191    227  36
   227    269  42
   269    313  44
   313    359  46
   359    409  50
   409    461  52
   461    521  60
   521    587  66
   587    659  72
   659    733  74
   733    809  76
   809    887  78
   887    967  80
   967   1049  82

Pascal

Library: primTrial

just showing the small difference to increasing prime gaps.
LastPrime is updated outside or inside If

<lang pascal> program NextSpecialprimes; //increasing prime gaps see //https://oeis.org/A002386 https://en.wikipedia.org/wiki/Prime_gap uses

 sysutils,
 primTrial;

procedure GetIncreasingGaps; var

 Gap,LastPrime,p : NativeUInt;

Begin

 InitPrime;
 Writeln('next increasing prime gap');
 writeln('Prime1':8,'Prime2':8,'Gap':4);
 Gap := 0;
 LastPrime := actPrime;
 repeat
   p := NextPrime;
   if p-LastPrime > Gap then
   Begin
     Gap := p-LastPrime;
     writeln(LastPrime:8,P:8,Gap:4);

   end;
   LastPrime := p;
 until LastPrime > 1000;

end;

procedure NextSpecial; var

 Gap,LastPrime,p : NativeUInt;

Begin

 InitPrime;
 Writeln('next special prime');
 writeln('Prime1':8,'Prime2':8,'Gap':4);
 Gap := 0;
 LastPrime := actPrime;
 repeat
   p := NextPrime;
   if p-LastPrime > Gap then
   Begin
     Gap := p-LastPrime;
     writeln(LastPrime:8,P:8,Gap:4);
     LastPrime := p;
   end;

 until LastPrime > 1000;

end;

begin

 GetIncreasingGaps;
 writeln;
 NextSpecial;

end.</lang>

Output:

next increasing prime gap
  Prime1  Prime2 Gap
       2       3   1
       3       5   2
       7      11   4
      23      29   6
      89      97   8
     113     127  14
     523     541  18
     887     907  20

next special prime
  Prime1  Prime2 Gap
       2       3   1
       3       5   2
       5      11   6
      11      19   8
      19      29  10
      29      41  12
      41      59  18
      59      79  20
      79     101  22
     101     127  26
     127     157  30
     157     191  34
     191     227  36
     227     269  42
     269     313  44
     313     359  46
     359     409  50
     409     461  52
     461     521  60
     521     587  66
     587     659  72
     659     733  74
     733     809  76
     809     887  78
     887     967  80
     967    1049  82

Phix

integer lastSpecial = 3, lastGap = 1
printf(1,"Special primes under 1,050:\n")
printf(1,"Prime1 Prime2 Gap\n")
printf(1,"%6d %6d %3d\n", {2, 3, lastGap})
for i=5 to 1050 by 2 do
    if is_prime(i) and (i-lastSpecial) > lastGap then
        lastGap = i - lastSpecial
        printf(1,"%6d %6d %3d\n", {lastSpecial, i, lastGap})
        lastSpecial = i
    end if
end for

Output:

Special primes under 1,050:
Prime1 Prime2 Gap
     2      3   1
     3      5   2
     5     11   6
    11     19   8
    19     29  10
    29     41  12
    41     59  18
    59     79  20
    79    101  22
   101    127  26
   127    157  30
   157    191  34
   191    227  36
   227    269  42
   269    313  44
   313    359  46
   359    409  50
   409    461  52
   461    521  60
   521    587  66
   587    659  72
   659    733  74
   733    809  76
   809    887  78
   887    967  80
   967   1049  82

<lang rexx>/*REXX program finds next special primes: difference of successive terms is increasing.*/ parse arg hi cols . /*obtain optional argument from the CL.*/ if hi== | hi=="," then hi= 1050 /* " " " " " " */ if cols== | cols=="," then cols= 10 /* " " " " " " */ call genP /*build array of semaphores for primes.*/ w= 10 /*width of a number in any column. */

                       @nsp= ' next special primes  < '      commas(hi)   ,
                             " such that the different of successive terms is increasing"

if cols>0 then say ' index │'center(@nsp , 1 + cols*(w+1) ) if cols>0 then say '───────┼'center("" , 1 + cols*(w+1), '─') op= @.1 /*assign oldPrime to the first prime.*/ nsp= 0; idx= 1 /*initialize number of nsp and index.*/ $= /*a list of nice primes (so far). */

    do j=0;       np= op + j                    /*assign newPrime to oldPrime  +  j    */
    if np>=hi         then leave                /*Is  newPrimeN ≥ hi?  Then leave loop.*/
    if \!.np          then iterate              /*Is  np  a prime?   Then skip this  J.*/
    nsp= nsp + 1                                /*bump the number of   nsp's.          */
    op= np                                      /*set oldPrime to the value of newPrime*/
    if cols==0        then iterate              /*Build the list  (to be shown later)? */
    c= commas(np)                               /*maybe add commas to the number.      */
    $= $ right(c, max(w, length(c) ) )          /*add a nice prime ──► list, allow big#*/
    if nsp//cols\==0  then iterate              /*have we populated a line of output?  */
    say center(idx, 7)'│'  substr($, 2);   $=   /*display what we have so far  (cols). */
    idx= idx + cols                             /*bump the  index  count for the output*/
    end   /*j*/

if $\== then say center(idx, 7)"│" substr($, 2) /*possible display residual output.*/ say say 'Found ' commas(nsp) @nsp exit 0 /*stick a fork in it, we're all done. */ /*──────────────────────────────────────────────────────────────────────────────────────*/ commas: parse arg ?; do jc=length(?)-3 to 1 by -3; ?=insert(',', ?, jc); end; return ? /*──────────────────────────────────────────────────────────────────────────────────────*/ genP: !.= 0 /*placeholders for primes (semaphores).*/

     @.1=2;  @.2=3;  @.3=5;  @.4=7;  @.5=11     /*define some low primes.              */
     !.2=1;  !.3=1;  !.5=1;  !.7=1;  !.11=1     /*   "     "   "    "     flags.       */
                       #=5;     s.#= @.# **2    /*number of primes so far;     prime². */
                                                /* [↓]  generate more  primes  ≤  high.*/
       do j=@.#+2  by 2  to hi                  /*find odd primes from here on.        */
       parse var j  -1 _; if     _==5  then iterate  /*J divisible by 5?  (right dig)*/
                            if j// 3==0  then iterate  /*"     "      " 3?             */
                            if j// 7==0  then iterate  /*"     "      " 7?             */
                                                /* [↑]  the above five lines saves time*/
              do k=5  while s.k<=j              /* [↓]  divide by the known odd primes.*/
              if j // @.k == 0  then iterate j  /*Is  J ÷ X?  Then not prime.     ___  */
              end   /*k*/                       /* [↑]  only process numbers  ≤  √ J   */
       #= #+1;    @.#= j;    s.#= j*j;   !.j= 1 /*bump # of Ps; assign next P;  P²; P# */
       end          /*j*/;   return</lang>

output when using the default inputs:

 index │            next special primes  <  1,050  such that the different of successive terms is increasing
───────┼───────────────────────────────────────────────────────────────────────────────────────────────────────────────
   1   │          2          3          5         11         19         29         41         59         79        101
  11   │        127        157        191        227        269        313        359        409        461        521
  21   │        587        659        733        809        887        967      1,049

Found  27  next special primes  <  1,050  such that the different of successive terms is increasing

Ring

<lang ring> load "stdlib.ring"

see "working..." + nl

Primes = [] limit1 = 100 oldPrime = 2

for n = 1 to limit1

   nextPrime = oldPrime + n
   if isprime(nextPrime)
      add(Primes,nextPrime)
      oldPrime = nextPrime
   ok

   diff = Primes[n+1] - Primes[n]
   see ""+ Primes[n] + "      " + Primes[n+1] + "    " + diff + nl

</lang>

Output:

working...
prime1 prime2  Gap
3          5     2
11        19     8
29        41    12
59        79    20
101      127    26
157      191    34
227      269    42
313      359    46
409      461    52
521      587    66
659      733    74
809      887    78
967      1049   82
done...

Wren

Library: Wren-math

Library: Wren-fmt

<lang ecmascript>import "/math" for Int import "/fmt" for Fmt

var primes = Int.primeSieve(1049) System.print("Special primes under 1,050:") System.print("Prime1 Prime2 Gap") var lastSpecial = primes[1] var lastGap = primes[1] - primes[0] Fmt.print("$6d $6d $3d", primes[0], primes[1], lastGap) for (p in primes.skip(2)) {

   if ((p - lastSpecial) > lastGap) {
       lastGap = p - lastSpecial
       Fmt.print("$6d $6d $3d", lastSpecial, p, lastGap)
       lastSpecial = p
   }

}</lang>

Output:

Special primes under 1,050:
Prime1 Prime2 Gap
     2      3   1
     3      5   2
     5     11   6
    11     19   8
    19     29  10
    29     41  12
    41     59  18
    59     79  20
    79    101  22
   101    127  26
   127    157  30
   157    191  34
   191    227  36
   227    269  42
   269    313  44
   313    359  46
   359    409  50
   409    461  52
   461    521  60
   521    587  66
   587    659  72
   659    733  74
   733    809  76
   809    887  78
   887    967  80
   967   1049  82