用动态规划
const
maxn=20;
var
n,m,i:byte;
ans,s:integer;
x:array[1..maxn] of longint;
f:array[1..10000] of byte;
p:array[1..1229] of integer;
procedure get-prime;
var
i,j,s:integer;
begin
s:=0;
f[1]:=0;
for i:=2 to 10000 do f:=1;
for i:=2 to 10000 do
if f=1 then begin
inc(s); p[s]:=i;
j:=2*i;
while j<=10000 do begin f[j]:=0 ; inc(j,i); end;
end
end;
procedure work(s:longint);
var
i:integer;
begin
if s<=10000 then inc(ans,f[s])
else begin
i:=1;
while sqr(longint(p))<=s do
begin
if s mod p=0 then exit;
inc(i)
end;
inc(ans)
end
end;
procedure search(d,pre:byte);
var
i:byte;
begin
for i:=pre+1 to n-(m-d) do
beign
inc(s,x);
if d=m then work(s)
else search(d+1,i);
dec(s,x)
end
end;
begin
readln(n,m);
for i:-1 to n do read(x);
ans:=0; s:=0;
get-prime;
search(1,0);
writeln(ans);
end.
