# Pretty Smooth Moves

In arithmetic, an n-smooth number, where n is a given prime number, is mathematically defined as a positive integer that has no prime factors greater than n. For example, 42 is 7-smooth because all its prime factors are less than or equal to 7, but 44 is not 7-smooth because it also has 11 as a prime factor.

Define a pretty smooth number as a number with no prime factors greater than its own square root. Thus, the list of pretty smooth numbers can be formulated as follows:

• (EDITED!) 1 is a pretty smooth number, due to its complete lack of any prime factors. (Note that in the original version of this question, 1 was erroneously excluded from the list, so if you exclude it from your outputs you won't be marked wrong.)
• Between 4 (= 22) and 8, the pretty smooth numbers are 2-smooth, meaning they have 2 as their only prime factor.
• Between 9 (= 32) and 24, the pretty smooth numbers are 3-smooth, and can have 2s and 3s in their prime factorizations.
• Between 25 (= 52) and 48, the pretty smooth numbers are 5-smooth, and can have 2s, 3s, and 5s in their prime factorizations.
• And so on, upgrading the criteria every time the square of the next prime number is reached.

The list of pretty smooth numbers is fixed, and begins as follows: 1, 4, 8, 9, 12, 16, 18, 24, 25, ...

Your challenge is to write code that will output all pretty smooth numbers up to and including 10,000 (= 1002). There must be at least one separator (it doesn't matter what kind -- space, comma, newline, anything) between each number in the list and the next, but it is completely irrelevant what character is used.

As per usual, lowest byte count wins -- obviously, simply outputting the list isn't going to be too beneficial to you here. Good luck!

• Why is 1 not pretty smooth? – Dennis Aug 15 '16 at 2:48
• Can we output the list in reverse order? – Leaky Nun Aug 15 '16 at 3:20
• OEIS A048098 (includes extra 1) – Leaky Nun Aug 15 '16 at 5:20
• @Mego "There are no pretty smooth numbers less than 4." is pretty clear. Not necessarily obvious, but definitely clear. – viraptor Aug 15 '16 at 10:40
• @viraptor It is voted as not clear not because it wasn't stated that 1 is not smooth, but because your definition and your exclusion statement contradict each other. – Leaky Nun Aug 15 '16 at 11:45

## Actually, 11 bytes

4╤R;yM²≤░


Try it online!

Does not include 1.

Explanation:

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


# Jelly, 12 bytes

Æf>½S
³²ḊÇÐḟ


Try it online!

### How it works

³²ḊÇÐḟ  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      Compute the prime factorization of n.
>½    Compare the prime factors with the square root of n.
S   Sum; add the resulting Booleans.


# Brachylog, 21 19 bytes

1 byte thanks to Fatalize, for inspiration of another 1 byte.

100^:4reP$ph^<=P@w\  Try it online! Takes about 6 seconds here. 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.  ## Previous 21-byte solution 100^:4reP'($pe^>P)@w\


Try it online!

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.

• 100^:4reP\$pot^<=P@w\ is one byte shorter, though less elegant. – Fatalize Aug 16 '16 at 7:10
• @Fatalize Thanks, I golfed off another byte – Leaky Nun Aug 16 '16 at 7:21

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


I don't have time to golf this now, but I want to illustrate a method for testing if n is pretty smooth: Multiply the numbers from 1 to sqrt(n) (i.e. compute a factorial), raise the product to a high power, and check if the result is a multiple of n.

Change to r=[2..10^4] if 1 should not be output.

• Not that it's any golfier, but I'm pretty sure the cube suffices (8 requires it). – Neil Aug 15 '16 at 8:38

# Pyth, 16 15 bytes

1 byte thanks to Jakube.

tf!f>*YYTPTS^T4


Try it 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)

• Surely Pyth has a square function? So you can replace *dd with that function? – Conor O'Brien Aug 15 '16 at 4:19
• @ConorO'Brien Nope, Pyth has not a square function. – Leaky Nun Aug 15 '16 at 4:21
• that seems like kind of an oversight – Conor O'Brien Aug 15 '16 at 4:23

## 05AB1E, 1614 13 bytes

4°L¦vyf¤yt›_—


Explanation

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


Try it online

• 4° is short for 10000. – Adnan Aug 15 '16 at 8:47
• @Adnan Thanks! Forgot about that one. – Emigna Aug 15 '16 at 8:50

## Matlab, 58575652 48 bytes

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


For each number it checks if all factors squared are not larger than the number itself. If yes, displays that number.

Thanks to @Luis Mendo for golfing this approach

Another approach (50 bytes):

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


For each number computes whether its maximum prime factor squared is less than the number itself. Then uses it for indexing.

• Your previous approach can be made shorter: for k=4:1e4,if factor(k).^2<=k,disp(k);end;end – Luis Mendo Aug 15 '16 at 14:56

# SQF, 252227 220

Standard script format:

#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]}}


Include the pre-processor in the compilation chain when calling eg:

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

This writes to the System Chat log, which is the closest thing SQF has to stdout

# C, 113 bytes

#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 it!

## Pyke, 1312 11 bytes

T4^S#DP#X<!


Try it here!

(Link only goes up to 10^3 because 10^4 times out)

T4^S        -  one_range(10^4)
#DP#X<! - filter_true(V, ^): (as i)
P     -   factors(i)
#X<! -  filter_true(V, ^):
X   -   ^ ** 2
<! -    not (i < ^)


# J, 20 bytes

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


Result:

   (#~{:@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...


Try it online here.

# Python 2, 90 bytes

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 it!

# R, 97 bytes

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


ungolfed

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)==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.


# Pyth, 12 bytes

g#^ePT2tS^T4


Does not include 1.