Если целое число больше 1, выведите количество способов, которыми оно может быть выражено как сумма одного или нескольких последовательных простых чисел.

Порядок слагаемых не имеет значения. Сумма может состоять из одного числа (поэтому выход для любого простого числа будет по крайней мере 1).

Это код-гольф . Стандартные правила применяются.

См. Эту вики OEIS для связанной информации и последовательностей, включая саму последовательность OEIS A054845 .

Контрольные примеры

2 => 1
3 => 1
4 => 0
5 => 2
6 => 0
7 => 1
8 => 1
10 => 1
36 => 2
41 => 3
42 => 1
43 => 1
44 => 0
311 => 5
1151 => 4
34421 => 6

Желе ,  6  5 байт

-1 благодаря Дилнану

ÆRẆ§ċ

Монадическая ссылка

Попробуйте онлайн! Или посмотрите набор тестов (обратите внимание, что окончательный тестовый случай истекает через 60 секунд в TIO).

Как?

ÆRẆ§ċ - Link: integer, n
ÆR    - primes from 2 to n inclusive
  Ẇ   - all contiguous substrings
   §  - sum each
    ċ - count occurrences of n

R , 95 байт

function(x,P=2){for(i in 2:x)P=c(P,i[all(i%%P)])
for(i in 1:x){F=F+sum(cumsum(P)==x)
P[i]=0}
F}

Попробуйте онлайн!

• -24 байта благодаря @Giuseppe, который в корне изменил мое решение, поддерживающее 34421!

05AB1E , 6 байтов

Код

ÅPŒOQO

Использует кодировку 05AB1E . Попробуйте онлайн!

JavaScript (ES6), 92 байта

n=>(a=[],k=1,g=s=>k>n?0:!s+g(s>0?s-(p=d=>k%--d?p(d):d<2&&a.push(k)&&k)(++k):s+a.shift()))(n)

Попробуйте онлайн!

комментарии

n => (                          // n = input
  a = [],                       // a[] = array holding the list of consecutive primes
  k = 1,                        // k = current number to test
  g = s =>                      // g = recursive function taking s = n - sum(a)
    k > n ?                     //   if k is greater than n:
      0                         //     stop recursion
    :                           //   else:
      !s +                      //     increment the final result if s = 0
      g(                        //     add the result of a recursive call to g():
        s > 0 ?                 //       if s is positive:
          s - (                 //         subtract from s the result of p():
            p = d => k % --d ?  //           p() = recursive helper function looking
              p(d)              //                 for the highest divisor d of k,
            :                   //                 starting with d = k - 1
              d < 2 &&          //           if d is less than 2 (i.e. k is prime):
              a.push(k) &&      //             append k to a[]
              k                 //             and return k (else: return false)
          )(++k)                //         increment k and call p(k)
        :                       //       else:
          s + a.shift()         //         remove the first entry from a[]
                                //         and add it to s
      )                         //     end of recursive call
  )(n)                          // initial call to g() with s = n

MATL, 15 12 байт

EZqPYTRYsG=z

Попробуйте это на MATL Online

Инициал E(умножьте на 2) гарантирует, что при вводе простых чисел результат функции последующего Ys( cumsum) не будет иметь повторяющегося простого ввода в обнуленной части матрицы (таким образом, вмешиваясь в счет).

Объяснение:

                % Implicit input, say 5
E               % Double the input
 Zq             % Get list of primes upto (and including) that
                %  Stack: [2 3 5 7]
   P            % Reverse that list
    YT          % Toeplitz matrix of that
                %  Stack: [7 5 3 2
                           5 7 5 3
                           3 5 7 5
                           2 3 5 7]
      R         % `triu` - upper triangular portion of matrix
                %  Stack: [7 5 3 2
                           0 7 5 3
                           0 0 7 5
                           0 0 0 7]
       Ys       % Cumulative sum along each column
                %  Stack: [7  5  3  2
                           7 12  8  5
                           7 12 15 10
                           7 12 15 17]


         G=     % Compare against input - 1s where equal, 0s where not
           z    % Count the number of non-zeros

Брахилог , 14 9 байт

{⟦ṗˢs+?}ᶜ

Попробуйте онлайн!
Несколько тестовых случаев

(-5 целых байтов, спасибо @Kroppeb!)

Объяснение:

{⟦ṗˢs+?}ᶜ
{      }ᶜ     Count the number of ways this predicate can succeed:
 ⟦            Range from 0 to input
  ṗˢ          Select only the prime numbers
    s         The list of prime numbers has a substring (contiguous subset)
     +        Whose sum
      ?       Is the input

Сетчатка 0.8.2 , 68 байт

.+
$*_$&$*
_
$`__¶
A`^(__+)\1+$
m)&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

Попробуйте онлайн! Ссылка включает в себя более быстрые тестовые случаи. Объяснение:

m)

Запустите весь скрипт в многострочном режиме, где ^и $соответствует каждой строке.

.+
$*_$&$*

Конвертировать в унарный дважды, сначала используя _s, затем используя 1s.

_
$`__¶

_$2$$n + 1$

A`^(__+)\1+$

Удалить все составные числа в диапазоне.

&`^((_)|¶)+¶[_¶]*(?<-2>1)+$(?(2)1)

__1$n$

Шелуха , 9 8 байт

^{-1 байт благодаря Mr.Xcoder (используйте именованный аргумент ¹вместо S)!}

#¹ṁ∫ṫ↑İp

Попробуйте онлайн!

объяснение

#¹ṁ∫ṫ↑İp  -- example input: 3
#¹        -- count the occurrences of 3 in
      İp  -- | primes: [2,3,5,7..]
     ↑    -- | take 3: [2,3,5]
    ṫ     -- | tails: [[2,3,5],[3,5],[5]]
  ṁ       -- | map and flatten
   ∫      -- | | cumulative sums
          -- | : [2,5,10,3,8,5]
          -- : 1

MATL , 16 байт

:"GZq@:g2&Y+G=vs

Попробуйте это в MATL Online!

объяснение

:"        % Input (implicit): n. For each k in [1 2 ... n]
  G       %   Push n
  Zq      %   Primes up to that
  @:g     %   Push vector of k ones
  2&Y+    %   Convolution, removing the edges
  G=      %   True for entries that equal n
  v       %   Concatenate vertically with previous results
  s       %   Sum
          % End (implicit). Display (implicit)

Python 2 , 106 104 байта

P=k=o=1
p=[]
i=input()
exec'o+=P%k*sum(p)==i;P*=k*k;k+=1;p+=P%k*[k];exec"p=p[i<sum(p):];"*k;'*i
print~-o

Попробуйте онлайн!

Чисто , 100 98 байт

import StdEnv,StdLib
$n=sum[1\\z<-inits[i\\i<-[2..n]|all(\j=i/j*j<i)[2..i-1]],s<-tails z|sum s==n]

Попробуйте онлайн!

Определяет функцию, $ :: Int -> Intкоторая работает как объяснено ниже:

$ n                              // the function $ of n is
    = sum [                      // the sum of
        1                        // 1, for every 
        \\ z <- inits [          // prefix z of 
            i                    // i, for every
            \\ i <- [2..n]       // integer i between 2 and n
            | and [              // where every
                i/j*j < i        // j does not divide i
                \\ j <- [2..i-1] // for every j between 2 and i-1
            ]
        ]
        , s <- tails z           // ... and suffix s of the prefix z
        | sum s == n             // where the sum of the suffix is equal to n
    ]

(Объяснение для более старой, но логически идентичной версии)

Perl 6 , 53 байта

{+grep $_,map {|[\+] $_},[\R,] grep *.is-prime,2..$_}

Попробуйте онлайн!

Использует оператор сокращения треугольника дважды. Последний контрольный пример слишком медленный для TIO.

объяснение

{                                                   } # Anonymous block
                               grep *.is-prime,2..$_  # List of primes up to n
                         [\R,]  # All sublists (2) (3 2) (5 3 2) (7 5 3 2) ...
          map {|[\+] $_},  # Partial sums for each, flattened
 +grep $_,  # Count number of occurrences

Japt, 17 байт

Должен быть более короткий путь, чем этот!

Выкладывает на последний контрольный пример.

õ fj x@ZãYÄ x@¶Xx

Попробуйте или запустите все тесты

объяснение

                      :Implicit input of integer U
õ                     :Range [1,U]
  fj                  :Filter primes
      @               :Map each integer at 0-based index Y in array Z
         YÄ           :  Y+1
       Zã             :  Subsections of Z of that length
             @        :  Map each array X
               Xx     :    Reduce by addition
              ¶       :    Check for equality with U
            x         :  Reduce by addition
     x                :Reduce by addition

Ява 10, 195 194 184 182 байта

n->{var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}for(x=L.size(),i=0;i<x;)for(k=i++,s=0;k<x;r+=s==n?1:0)s+=(int)L.get(k++);return r;}

-1 байт благодаря @ceilingcat .
-10 байт благодаря @SaraJ .

Попробуйте онлайн.

Объяснение:

n->{                // Method with integer as both parameter and return-type
  var L=new java.util.Stack();
                    //  List of primes, starting empty
  int i=1,k,x,s,    //  Temp integers
      r=0;          //  Result-counter, starting at 0
  for(;i++<n;){     //  Loop `i` in the range [2, `n`]
    for(k=1;        //   Set `k` to 1
        i%++k>0;);  //   Inner loop which increases `k` by 1 before every iteration,
                    //   and continues as long as `i` is not divisible by `k`
    if(k==i)        //   If `k` is now still the same as `i`; a.k.a. if `i` is a prime:
      L.add(i);}    //    Add the prime to the List
  for(x=L.size(),   //  Get the amount of primes in the List
      i=0;i<x;)     //  Loop `i` in the range [0, amount_of_primes)
    for(s=0,        //   (Re)set the sum to 0
        k=i++;k<x;  //   Inner loop `k` in the range [`i`, amount_of_primes)
        r+=s==n?    //     After every iteration, if the sum is equal to the input:
            1       //      Increase the result-counter by 1
           :        //     Else:
            0)      //      Leave the result-counter the same by adding 0
      s+=(int)L.get(k++);
                    //    Add the next prime (at index `k`) to the sum
  return r;}        //  And finally return the result-counter

Это в основном похоже на ответы Jelly или 05AB1E , всего на 190 байт больше .. XD
Вот сравнение для каждой из частей, добавленное просто для забавы (и чтобы увидеть, почему Java такая многословная, и эти языки игры в гольф такие мощные):

1. Возьмем ввод: (Jelly: 0 байт) неявно ; (05AB1E: 0 байт) неявно ; (Java 10: 5 байт)n->{}
2. Создайте список простых чисел в диапазоне [2, n]: (желе: 2 байта) ÆR; (05AB1E: 2 байта) ÅP; (Java 10: 95 байт)var L=new java.util.Stack();int i=1,k,x,s,r=0;for(;i++<n;){for(k=1;i%++k>0;);if(k==i)L.add(i);}
3. Получить все непрерывные подсписки: (Jelly: 1 байт) Ẇ; (05AB1E: 1 байт) Œ; (Java 10: 55 байт) for(x=L.size(),i=0;i<x;)for(k=i++;k<x;)и(int)L.get(k++);
4. Суммируйте каждый подсписок: (Желе: 1 байт) §; (05AB1E: 1 байт) O; (Java 10: 9 байт) ,sи ,s=0иs+=
5. Подсчитайте те, которые равны входу: (Желе: 1 байт) ċ; (05AB1E: 2 байта) QO; (Java 10: 15 байт) ,r=0иr+=s==n?1:0
6. Выведите результат: (Jelly: 0 байтов) неявно ; (05AB1E: 0 байт) неявно ; (Java 10: 9 байт)return r;

Физика , 41 байт

->x:Count[Sum@Sublists[PrimeQ$$[…x]];x]

Попробуйте онлайн!

Как это устроено

->x:Count[Sum@Sublists[PrimeQ$$[…x]];x] // Full program.
->x:            // Define an anonymous function with parameter x.
    […x]        // Range [0 ... x] (inclusive).
        $$      // Filter-keep those that...
  PrimeQ        // Are prime.
 Sublists[...]  // Get all their sublists.
Sum@            // Then sum each sublist.
Count[...;x]    // Count the number of times x occurs in the result.

Haskell , 89 байт

g n=sum[1|a<-[0..n],_<-filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]]

Попробуйте онлайн!

Альтернатива, 89 байт

f n=length$do a<-[0..n];filter(n==).scanl1(+)$drop a[p|p<-[2..n],all((>0).mod p)[2..p-1]]

Попробуйте онлайн!