Imprimer les nombres premiers manquants

18

La tâche

Écrivez un programme ou une fonction qui, une fois entrée numérique x, imprime ou renvoie les nombres premiers sous la racine carrée de x1 qui ne sont pas des facteurs de x.

Exemples

Soit f(x)la fonction appelée:

>>> f(4)
[]

>>> f(5)
[2]

>>> f(20)
[3]

>>> f(60)
[7]

>>> f(100)
[3, 7]

>>> f(10000)
[3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Règles de bonus

  • Vous pouvez utiliser n'importe quel module intégré fourni par votre langue.
  • Votre programme doit prendre en charge une xentrée aussi haute que la limite supérieure définie par votre langue.

1 L' utilisation de la racine carrée comme seuls nombres premiers en dessous de la racine carrée peut réellement être impliquée dans les facteurs de x. Sans cette restriction, les grands nombres auraient beaucoup de nombres imprimés en excès.

code-golf number primes Addison Crump
la source
3
"Seuls les nombres premiers au-dessous de la racine carrée peuvent réellement être impliqués dans les facteurs de x" n'est pas vrai: un nombre peut avoir un facteur premier plus grand que sa racine carrée. En effet, vos deux premiers exemples (5 et 20) ont cette propriété, comme tous les nombres premiers, deux fois tous les nombres impairs, ....
Greg Martin
1
@GregMartin Oui, ils peuvent - mais ils ne peuvent pas être trouvés dans la première moitié des facteurs. Il est logique de ne pas inclure 7 dans les nombres premiers manquants de 48 car 7 ^ 2 est supérieur à 48. (mon raisonnement est là)
Addison Crump

Réponses:

8

Jelly, 6 octets dans la page de codes de Jelly

½ÆRḟÆf

Essayez-le en ligne!

Explication:

½ÆRḟÆf
 ÆR    All primes less than or equal to
½      the square root of the input
   ḟ   but with the following removed:
    Æf All prime factors of {the input, by default}

la source
5
Les réponses de Jelly décrivent souvent littéralement le défi: P
ETHproductions
6

MATL , 10 9 octets

X^ZqGYfX-

Essayez-le en ligne!

Explication

X^    % Implicit input. Square root
Zq    % Array if primes up to that
G     % Push input again
Yf    % Array of prime factors
X-    % Set difference. Implicit display
Luis Mendo
la source
5

MATLAB, 57 54 octets

function h(p);a=primes(p^.5);a(~ismember(a,factor(p)))

Assez simple, obtient un tableau de nombres premiers jusqu'à sqrt (p) puis supprime ceux qui sont également des facteurs de p. Imprime la sortie de la dernière ligne par défaut car le point-virgule est laissé de côté.

MattWH
la source
1
Je n'ai jamais essayé MATLAB, mais d'après ce que j'ai lu à ce sujet, sqrt (p) peut être écrit comme p ^ 0,5 ou peut-être p ^ .5 bien que je ne sois pas sûr de la deuxième suggestion
t-clausen.dk
Agréable! :) J'ai posté une soumission Octave en utilisant la même approche.
Stewie Griffin
4

Pyth, 10 octets

fP_T-S@Q2P

Un programme qui prend l'entrée d'un nombre et imprime une liste.

Suite de tests

Comment ça fonctionne

fP_T-S@Q2P   Program. Input: Q
fP_T-S@Q2PQ  Implicit input fill
f            Filter
     S@Q2    the 1-indexed range up to floor(sqrt(Q))
    -    PQ  with the prime factors of Q removed
 P_T         by primality
             Implicitly print
TheBikingViking
la source
4

05AB1E , 8 octets

tLDpϹfK

Essayez-le en ligne!

Explication

tL        # range [1 ... sqrt(input)]
  DpÏ     # keep only primes
     ¹fK  # remove factors of input
Emigna
la source
3

PHP, 76 octets

for($n=1;++$n*$n<$x=$argv[1];){for($i=$n;$n%--$i;);if($i<2&&$x%$n)echo$n,_;}

utilise ma solution is_prime pour $ n> 1

prend l'entrée de l'argument de ligne de commande. Courez avec -r.

Titus
la source
2

Mathematica, 46 octets

Select[Prime@Range@PrimePi@Sqrt[a=#],!#∣a&]&

Fonction anonyme. Prend un nombre en entrée et renvoie une liste de nombres en sortie. Le caractère Unicode est U + 2223 DIVIDES pour \[Divides].

LegionMammal978
la source
2

Ruby, 55 octets

require'prime'
->x{Prime.to_a(x**0.5).select{|n|x%n>0}}

Une réponse plutôt paresseuse en utilisant l'énumérateur principal intégré.

JayDepp
la source
2

Wonder , 14 octets

@(_> > ^#0.5)P

Usage:

(@(_> > ^#0.5)P)10

Prend les éléments d'une liste infinie de nombres premiers tandis que l'élément est inférieur à la racine carrée de l'argument.

Mama Fun Roll
la source
2

Pyke, 10 octets

,BS#_P)QP-

Essayez-le ici!

,B         -    int(sqrt(input))
  S        -   range(1, ^+1)
   #_P)    -  filter(^, is_prime)
         - - ^.remove(V)
       QP  -  factors(input)
Bleu
la source
2

PowerShell v2 +, 71 octets

param($n)1..[math]::Sqrt($n)|?{$n%$_-and'1'*$_-match'^(?!(..+)\1+$)..'}

Solution itérative. Prend une entrée $net crée une plage de 1à Sqrt($n)(notez que l'opérateur de plage va implicitement convertir l'extrémité supérieure en un [int]qui fera l'arrondi de banquier par défaut). Utilise ensuite |?{...}(l' Where-Objectopérateur, qui agit comme un filtre) pour extraire les nombres où $n%$_est non nul (c.-à-d., Tout reste du modulo signifie que ce n'est pas un facteur, et que tout non nul est vrai) -andle test prime regex habituel est $true. Ceux-ci sont laissés sur le pipeline et la sortie est implicite.

Exemples

(avec un formatage supplémentaire pour améliorer la sortie)

PS C:\Tools\Scripts\golfing> 5,20,60,100,10000|%{"f($_)";(.\print-the-missing-primes.ps1 $_)-join', ';""}
f(5)
2

f(20)
3

f(60)
7

f(100)
3, 7

f(10000)
3, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

NB - Cela échouera sur les versions antérieures si l'entrée est plus grande qu'autour 2500000000, car l' ..opérateur de plage ne peut prendre en charge que jusqu'à 50 000 éléments. Mais, puisque c'est plus grand que la valeur [int]maximale du type de données par défaut 2147483647, je suppose que c'est OK. Sur ma machine, PSv4 Win8.1, cependant, je peux aller plus haut, mais je ne trouve pas de documentation expliquant la différence.

AdmBorkBork
la source
2

JavaScript (ES6), 79 76 octets

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]

Sur la base de mon fonction de test de primalité récursive . Je pense qu'il devrait y avoir quelques façons de simplifier cela, mais je ne peux pas comprendre comment ...

Extrait de test

f=(q,n=2,x=n)=>n*n<q?[...--x<2&&q%n?[n]:[],...x>1&&n%x?f(q,n,x):f(q,n+1)]:[]
<input type="number" step=1 min=4 value=4 oninput="O.innerHTML='['+f(this.value)+']'"><br>
<pre id=O>[]</pre>
Développer l'extrait

ETHproductions
la source
2

Octave, 44 octets

Cette réponse est inspirée de la réponse MATLAB de MattWH , mais je l'ai utilisée en utilisant certaines fonctionnalités spécifiques à Octave.

@(x)(y=primes(x^.5))(~ismember(y,factor(x)))

Il s'agit d'une fonction anonyme qui prend l'entrée x. Octave a une affectation et une indexation des variables en ligne permettant yd'être d'abord créées dans la fonction (pas possible dans MATLAB), puis utilisées dans le cadre du masque logique créé par ismember(là encore, impossible de le faire de cette façon dans MATLAB).

Stewie Griffin
la source
Très sympa, devra se pencher sur Octave. Ces fonctionnalités seraient utiles pour le golf!
MattWH
1

Perl 6 , 37 octets

{grep {$^a.is-prime&$_%$a},2.. .sqrt}

Étendu:

{   # bare block lambda with implicit parameter ｢$_｣

  grep
  {
    $^a.is-prime  # check if it is prime
    &             # and junction
    $_ % $a       # check if the input is not evenly divisible by it
  },
  2.. .sqrt          # Range of values up-to and including squareroot
}
Brad Gilbert b2gills
la source
1

TSQL, 130 octets

DECLARE @v int=10000

,@ INT=2SELECT 2p INTO #
g:INSERT # SELECT @ FROM # HAVING isnull(min(@%p),1)>0SET @+=1IF @*@<@v GOTO g
SELECT*FROM # WHERE @v%p>0

Cela ne s'exécutera qu'une seule fois, puis vous devrez supprimer la table temporaire pour l'exécuter à nouveau dans le même éditeur

DROP TABLE #

J'ai fait une version pour la tester, elle est un peu plus longue car les permissions en ligne pour créer des tables ne sont pas disponibles. Pour la même raison, il n'a cependant pas besoin de la table de dépôt.

Essayez-le en ligne

t-clausen.dk
la source
1

R, 58 63 octets

for(i in 2:sqrt(x<-scan()))if(x%%i&numbers::isPrime(i))print(i)

Boucle sur toutes les valeurs de 2 à sqrt(x)et vérifie si elles sont premières avec le numberspackage. x%%icalcule x mod iqui est 0 -> Falsesi iest un diviseur de xet >0 -> Truesii ne l'est pas.

+5 octets car la numbers::Primes(n)fonction n'autorise pas les décimales, tout en 2:sqrt(x)fonctionnant, ajout d'une vérification principale à l' ifinstruction.

JAD
la source
1

Haskell, 55 54 octets

f x=[y|y<-[2..x],y*y<x,[z|z<-[1..y],gcd(z*x)y>1]==[y]]

Compréhensions de listes imbriquées généralement simples. GCD remplit deux rôles, testant si les nombres en dessous de y sont des facteurs de y et testant également si y est un facteur de x.

Espacé un peu:

f x = [ y|y<-[2..x],     y*y<x,     [z|z<-[1..y], gcd (z*x) y > 1] == [y] ]
James Hollis
la source
Enregistrez un octet avec gcd(z*x)y>1.
Zgarb
J'ai également mis la vérification y * y <x en premier pour le rendre un peu plus rapide.
James Hollis
0

Rétine , 69 66 octets

.+
$*
(11\1|^1)+
$#1$*1:$&
M!&`(?!(11+)\1+:)(1+):(?!\2+$)
M%`1
^0

Imprime les nombres premiers sur des lignes séparées, du plus grand au plus petit.

Essayez-le en ligne! (Cela prend environ 10 secondes en raison des deux derniers cas de test. L'en-tête et le pied de page permettent une suite de tests séparés par un saut de ligne et convertissent la sortie en virgule de séparation pour plus de lisibilité.)

Explication

.+
$*

Convertissez l'entrée en unaire.

(11\1|^1)+
$#1$*1:$&

Cela ajoute la racine carrée de l'entrée, séparée par :. La racine carrée est calculée sur la base du fait que le carré de nest également la somme des premiers nentiers impairs. Nous pouvons faire correspondre des entiers impairs consécutifs avec la référence directe (11\1|^1). Dans le processus, le groupe sera utilisé exactement nfois, où nest le plus grand nombre dont le carré s'inscrit dans l'entrée.

Nous insérons une représentation unaire de ce nombre avec $#1$*1, suivie d'un deux-points et de la correspondance elle-même.

M!&`(?!(11+)\1+:)(1+):(?!\2+$)

Cela correspond à tous les nombres premiers manquants qui correspondent à la racine carrée. La détection de prime est basée sur l'expression rationnelle de vérification de prime standard , puis nous nous assurons simplement que le premier que nous venons de capturer ne divise pas l'entrée avec le deuxième lookahead. En utilisant l' &option, nous obtenons des correspondances qui se chevauchent pour garantir que nous obtenons tous les nombres premiers.

M%`1

Ceci convertit chaque ligne (c'est-à-dire chaque nombre premier manquant) en décimal en faisant correspondre le nombre de 1s. Le seul problème est que cela insère un zéro si aucun nombre premier manquant n'a été trouvé.

^0

Cette étape supprime donc ce zéro s'il a été ajouté.

Martin Ender
la source