Dość płynne ruchy

18

W arytmetyce liczba n-gładka , gdzie n jest daną liczbą pierwszą, jest matematycznie zdefiniowana jako dodatnia liczba całkowita, która nie ma czynników pierwszych większych niż n. Na przykład 42 ma 7-gładkość, ponieważ wszystkie jego czynniki pierwsze są mniejsze lub równe 7, ale 44 nie jest 7-gładkie, ponieważ ma również 11 jako czynnik pierwszy.

Zdefiniuj całkiem gładką liczbę jako liczbę bez czynników pierwszych większych niż jej pierwiastek kwadratowy. Tak więc listę całkiem gładkich liczb można sformułować w następujący sposób:

  • (ZMIENIONO!) 1 jest dość gładką liczbą, z powodu całkowitego braku jakichkolwiek czynników pierwszych. (Pamiętaj, że w oryginalnej wersji tego pytania 1 zostało błędnie wykluczone z listy, więc jeśli wykluczysz je z wyników, nie zostaniesz źle oznaczony).
  • Pomiędzy 4 (= 2 2 ) a 8 dość gładkie liczby są 2-gładkie, co oznacza, że ​​mają 2 jako jedyny czynnik pierwszy.
  • Pomiędzy 9 (= 3 2 ) a 24, dość gładkie liczby są 3-gładkie i mogą mieć 2s i 3s w swoich głównych faktoryzacjach.
  • Pomiędzy 25 (= 5 2 ) a 48, całkiem gładkie liczby są 5-gładkie i mogą mieć 2s, 3s i 5s w swoich głównych faktoryzacjach.
  • I tak dalej, aktualizowanie kryteriów za każdym razem, gdy zostanie osiągnięty kwadrat następnej liczby pierwszej.

Lista całkiem gładkich liczb jest stała i zaczyna się następująco: 1, 4, 8, 9, 12, 16, 18, 24, 25, ...

Twoim wyzwaniem jest napisanie kodu, który wyświetli wszystkie całkiem gładkie liczby do 10.000 włącznie (= 100 2 ). Musi istnieć co najmniej jeden separator (nie ma znaczenia, jakiego rodzaju - spacja, przecinek, nowa linia, cokolwiek) między każdą liczbą na liście i następną, ale nie ma znaczenia, jaki znak jest używany.

Jak zwykle wygrywa najniższa liczba bajtów - oczywiście, samo przedstawienie listy nie będzie dla ciebie zbyt korzystne. Powodzenia!

A. Mirabeau
źródło
9
Dlaczego 1 nie jest całkiem gładki?
Dennis
Czy możemy wydrukować listę w odwrotnej kolejności?
Leaky Nun
5
OEIS A048098 (zawiera dodatkowe 1)
Leaky Nun
1
@Mego „Nie ma dość gładkich liczb mniejszych niż 4.” jest całkiem jasne. Niekoniecznie oczywiste, ale zdecydowanie jasne.
viraptor
1
@viraptor Głosowano jako niejasne nie dlatego, że nie stwierdzono, że 1 nie jest gładka, ale ponieważ twoja definicja i oświadczenie o wykluczeniu są ze sobą sprzeczne.
Leaky Nun

Odpowiedzi:

1

Właściwie 11 bajtów

4╤R`;yM²≤`░

Wypróbuj online!

Nie obejmuje 1.

Wyjaśnienie:

4╤R`;yM²≤`░
4╤R          range(10**4)
   `;yM²≤`░  filter: take values where
    ;yM²       the square of the largest prime factor
        ≤      is less than or equal to the value
Mego
źródło
7

Galaretka , 12 bajtów

Æf>½S
³²ḊÇÐḟ

Wypróbuj online!

Jak to działa

³²ḊÇÐḟ  Main link. No arguments.

³       Yield 100.
 ²      Square it to yield 10,000.
  Ḋ     Dequeue; yield [2, ..., 10,000].
   ÇÐḟ  Filter-false; keep elements for which the helper link returns 0.

Æf>½S   Helper link. Argument: n

Æf      Compute the prime factorization of n.
  >½    Compare the prime factors with the square root of n.
    S   Sum; add the resulting Booleans.
Dennis
źródło
7

Brachylog , 21 19 bajtów

1 bajt dzięki Fatalize dla inspiracji kolejnego 1 bajtu.

100^:4reP$ph^<=P@w\

Wypróbuj online!

Zajmuje tutaj około 6 sekund.

100^:4reP$ph^<=P@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P$ph^<=P         P, prime factorized (from biggest to smallest),
                         take the first element, squared, is less than
                         or equal to P
               P@w       Write P with a newline,
                  \      Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.

Poprzednie 21-bajtowe rozwiązanie

100^:4reP'($pe^>P)@w\

Wypróbuj online!

Zajmuje tutaj około 6 sekund.

100^:4reP'($pe^>P)@w\
100                      100
   ^                     squared
    :4                   [10000,4]
      r                  [4,10000]
       eP                P is an integer in that interval (choice point),
        P'(      )       The following about P cannot be proved:
           $pe               one of its prime factor
              ^              squared
               >P            is greater than P
                  @w     Write P with a newline,
                    \    Backtrack to the last choice point and make
                         a different choice until there is no more
                         choice and the program halts.
Leaky Nun
źródło
100^:4reP$pot^<=P@w\jest o jeden bajt krótszy, ale mniej elegancki.
Fatalize
@Ugratuj Dzięki, grałem w inny bajt
Leaky Nun
4

Haskell, 53 bajty

r=[1..10^4]
[n|n<-r,product[x|x<-r,x*x<=n]^n`mod`n<1]

Nie mam teraz czasu na grę w golfa, ale chcę zilustrować metodę sprawdzania, czy njest dość płynna: pomnóż liczby od 1do sqrt(n)(tj. Oblicz silnię), podnieś produkt do dużej mocy i sprawdź, czy wynik jest wielokrotnościąn .

Zmień na r=[2..10^4]jeśli 1nie powinno być wyprowadzane.

xnor
źródło
Nie chodzi o to, że jest golfistą, ale jestem pewien, że kostka wystarczy ( 8wymaga).
Neil,
2

Pyth , 16 15 bajtów

1 bajt dzięki Jakube.

tf!f>*YYTPTS^T4

Wypróbuj online!

tf!f>*YYTPTS^T4
             T   10
            ^T4  10000
           S^T4  [1,2,3,...,10000]
 f               filter for elements as T for
                 which the following is truthy: 
         PT          prime factorization of T
   f                 filter for factor as Y:
     *YY                 Y*Y
    >   T                greater than T ?
  !                  logical negation
t                remove the first one (1)
Leaky Nun
źródło
Z pewnością Pyth ma kwadratową funkcję? Więc możesz zastąpić *dd tą funkcją?
Conor O'Brien
@ ConorO'Brien Nie, Pyth nie ma kwadratowej funkcji.
Leaky Nun
to wydaje się rodzajem niedopatrzenia
Conor O'Brien
2

05AB1E, 16 14 13 bajtów

4°L¦vyf¤yt›_—

Wyjaśnienie

4°L¦v             # for each y in range 2..10000
      yf¤         # largest prime factor of y
         yt       # square root of y
           ›_     # less than or equal
             —    # if true then print y with newline

Wypróbuj online

Emigna
źródło
jest skrótem od 10000.
Adnan
@Adnan Thanks! Zapomniałem o tym.
Emigna
2

Matlab, 58 57 56 52 48 bajtów

for k=1:1e4
if factor(k).^2<=k
disp‌​(k)
end
end

Dla każdej liczby sprawdza, czy wszystkie czynniki do kwadratu nie są większe niż sama liczba. Jeśli tak, wyświetla ten numer.

Dzięki @Luis Mendo za grę w golfa


Inne podejście (50 bajtów):

n=1:10^4;for k=n
z(k)=max(factor(k))^2>k;end
n(~z)

Dla każdej liczby oblicza, czy jej maksymalny współczynnik pierwszy podniesiony do kwadratu jest mniejszy niż sama liczba. Następnie używa go do indeksowania.

pajonk
źródło
1
Poprzednie podejście można skrócić:for k=4:1e4,if factor(k).^2<=k,disp(k);end;end
Luis Mendo
1

SQF , 252 227 220

Standardowy format skryptu:

#define Q(A,B) for #A from 2 to B do{
Q(i,10000)if([i]call{params["j"];u=sqrt j;a=true;Q(k,u)a=a and((j%k!=0)or(j/k<u)or!([j/k]call{params["x"];q=true;Q(z,sqrt x)q=q and(x%z!=0)};q}))};a})then{systemChat format["%1",i]}}

Uwzględnij preprocesor w łańcuchu kompilacji podczas wywoływania, np .:

  • execVM "FILENAME.sqf"
  • call compile preprocessFile "FILENAME.sqf"

Zapisuje to w dzienniku czatu systemowego, który jest najbliższym wyjściem SQF

Obrzydliwe
źródło
1

C, 113 bajtów

#include<stdio.h>
main(a){for(;++a<10001;){int n=2,c=a;for(;n*n<=a;n++)while(c%n<1)c/=n;if(c<2)printf("%d ",a);}}

Ideone to!

Leaky Nun
źródło
1

Pyke, 13 12 11 bajtów

T4^S#DP#X<!

Wypróbuj tutaj!

(Link zwiększa się tylko do 10 ^ 3, ponieważ przekroczono limit 10 ^ 4)

T4^S        -  one_range(10^4)
    #DP#X<! - filter_true(V, ^): (as i)
      P     -   factors(i)
       #X<! -  filter_true(V, ^):
        X   -   ^ ** 2
         <! -    not (i < ^)
niebieski
źródło
1

J, 20 bajtów

(#~{:@q:<:%:)2+i.1e4

Wynik:

   (#~{:@q:<:%:)2+i.1e4
4 8 9 12 16 18 24 25 27 30 32 36 40 45 48 49 50 54 56 60 63 64 70 72 75 80...

Wypróbuj online tutaj.

randomra
źródło
0

Python 2, 90 bajtów

for i in range(4,10001):
 n=2;j=i
 while n*n<=j:
  while i%n<1:i/=n
  n+=1
 if i<2:print j

Ideone to!

Leaky Nun
źródło
0

R, 97 bajtów

b=F;for(j in 1:1e4){for(i in which(!j%%1:j)[-1])if(which(!i%%1:i)[2]==i)b=i<=j^0.5;if(b)print(j)}

bez golfa

b <- F                               #Initializes
for (j in 1:1e4){                    #Loop across integers 1..10^4
    a <- which(!j%%1:j)[-1]          #Finds all factors
    for (i in a)                     #Loop across factors
         b <- which(!i%%1:i)[2]==i   #Tests primeness
         if(b) c <- i<=j^0.5         #If prime, tests smoothness
    if(c) print(j)                   #If biggest prime factor gives smooth
}                                    #result, Prints the number.
użytkownik5957401
źródło
0

Pyth, 12 bajtów

g#^ePT2tS^T4

Nie obejmuje 1.

isaacg
źródło