[Question]
  [
Given an integer **1 ≤ N ≤ 1,000,000** as input, output the last non-zero digit of **N!**, where **!** is the factorial (the product of all numbers from **1** to **N**, inclusive). This is OEIS sequence [A008904](//oeis.org/A008904).
Your program needs finish within 10 seconds on a reasonable machine for any valid input.
# Test Cases
```
1 => 1
2 => 2
3 => 6
4 => 4
5 => 2
6 => 2
7 => 4
8 => 2
9 => 8
10 => 8
100 => 4
1000 => 2
10000 => 8
100000 => 6
1000000 => 4
```
This is a [code-golf](/questions/tagged/code-golf "show questions tagged 'code-golf'") so the shortest code in bytes wins!
  
[Answer]
## Mathematica, ~~45~~ 36 bytes
```
Last@Select[IntegerDigits[#!],#>0&]&
```
Very readable for a winning answer. :) (Then again, there's no GolfScript & Co. submission yet.)
This handles input 1,000,000 in about 5 seconds on my machine.
[Answer]
# Ruby - 63 chars
```
f=->n{n<2?1:6*[1,1,2,6,4,4,4,8,4,6][n%10]*3**(n/5%4)*f[n/5]%10}
```
Source - <http://oeis.org/A008904>
Handles f upto a thousand digits under a second.
# Test
```
irb(main):014:0> for n in 2..6
irb(main):015:1> puts f[10**n]
irb(main):016:1> end
4
2
8
6
4
```
[Answer]
## Python - 75
```
n=input()
g=1
while n:
 g*=n
 while g%10<1:g/=10
 g%=10**9
 n-=1
print g%10
```
[Answer]
## PARI/GP - 27 bytes
This trades speed for size -- the testcase takes a long time (~6 seconds).
```
n->n!/10^valuation(n!,5)%10
```
This version is much faster (~15 microseconds) but takes 81 bytes:
```
n->r=1;while(n,r*=Mod(4,10)^(n\10%2)*[1,2,6,4,2,2,4,2,8][max(n%10,1)];n\=5);lift(r)
```
You can use this (non-golfed) code to test either:
```
[%(10^n) | n <- [1..6]]
```
[Answer]
# JavaScript, 59 bytes
Based on [this answer](https://math.stackexchange.com/a/130389/1156907)
```
f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]
```
Try it:
```
f=n=>n>9?'6248'[(a=n/5|0)%4]*f(a)*f(n%5)%10:'1126422428'[n]
;[
  0, // 1
  1, // 1
  2, // 2
  3, // 6
  4, // 4
  5, // 2
  6, // 2
  7, // 4
  8, // 2
  9, // 8
  10, // 8
  20, // 4
  100, // 4
  1000, // 2
  10000, // 8
  100000, // 6
  1000000, // 4
].forEach(n=>console.log(n, f(n)))
```
Modified formula is:
$$
D(0) = 1 \\
D(1) = 1 \\
D(2) = 2 \\
D(3) = 6 \\
D(4) = 4 \\
D(5) = 2 \\
D(6) = 2 \\
D(7) = 4 \\
D(8) = 2 \\
D(9) = 8 \\
D(n) = (LastDigitOf(2^{\lfloor n/5 \rfloor}) \* D(\lfloor n/5 \rfloor) \* D(n \mod 5)) \mod 10, \;where \;n > 9
$$
## How?
The original formula is \$D(n) = (2^{[n/5]} \* D([n/5]) \* D(n \mod 5)) \mod 10\$
But there is a problem: we need to calculate \$2^{[n/5]}\$. For example if \$n = 10 000 \$ then we need to calculate \$2^{2000}\$ which is already too hard (in JS it will output `Infinity`). But I discovered that we don't need to calculate it instead of this we just need to calculate the last digit of \$2^{[n/5]}\$. Why? Because each time we just need to calculate the last digit of \$2^{[n/5]} \* D([n/5]) \* D(n \mod 5)\$
### Theorem
The last digit of multiplication is the last digit of multiplication of last digits of each multiplier
### Proof
Let's say we have two numbers \$a\$ and \$b\$. We can represent each of them to the power of `10`:
$$
a = x\_n \* 10^n + x\_{n - 1} \* 10^{n - 1} + \ldots + x\_1 \* 10^1 + x\_0 \\
b = y\_n \* 10^m + y\_{m - 1} \* 10^{m - 1} + \ldots + y\_1 \* 10^1 + y\_0
$$
or
$$
a = (x\_n \* 10^{n - 1} + x\_{n - 1} \* 10^{n - 2} + \ldots + x\_1) \* 10 + x\_0 \\
b = (y\_n \* 10^{m - 1} + y\_{m - 1} \* 10^{m - 2} + \ldots + y\_1) \* 10 + y\_0
$$
When we multiply them we will get:
$$
a \* b = (...) \* 10 + x\_0 \* y\_0
$$
Now it is clear that the last digit of multiplication is the last digit of \$x\_0 \* y\_0\$, where the \$x\_0\$ and \$y\_0\$ are the last digits of \$a\$ and \$b\$ respectively. So we proved the theorem
Now we need to find the last digits of powers of `2`. Let's write some of them:
$$
2^0 = 1 \\
2^1 = 2 \\
2^2 = 4 \\
2^3 = 8 \\
2^4 = 16 \\
2^5 = 32 \\
2^6 = 64 \\
2^7 = 128 \\
2^8 = 256
$$
Now we can see the pattern `1 (2 4 8 6) (2 4 8 6)` and can write it \$(k = [n / 5])\$:
```
if (k == 0) return 1;
else return [6, 4, 8, 7][k % 4];
```
We can ignore the first case when `k == 0` and here is why:
`k % 4 == 0` when `k is one of [0, 4, 8, 12, 16, ...]` but we need to consider cases when `k is one of [0, 4, 8]` because for bigger values we will run recursion. The second multiplier in our formula is \$D(k)\$ and for `k is on of [0, 4, 8]` we get `[1, 4, 2]` respectively. We had to multiply these values by `1` but instead of this we will multiply them by `6` so we will get `[1, 24, 12]`, the last digits of these values are `[1, 4, 2]`. Now we can see that it doesn't matter to multiply them by `1` or `6` the last digits will be the same
The last thing we need it is to prove that \$[n / 5] = \lfloor n / 5 \rfloor\$ for \$n \ge 0\$. I think it is obvious
[Answer]
# Perl, 53 ~~58~~ ~~61~~ characters
All whitespace can be removed, but I left it in for "readability". Note: not using some silly explicit formula from Sloane.
```
sub f {
    $_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $_[0];
    $1 % 10
}
```
Calculates f(10^6) in 8.7 seconds on my machine.
**Update**: OP wanted it to be a whole program:
```
$_ = $1 * ++$n || 1, /(.{1,7}?)0*$/ while $n < $ARGV[0];
print $1 % 10
```
That makes it 55 characters.
[Answer]
# CJam - 28
```
1ri{I)*_AbW%{}#A\#/1e7%}fIA%
```
You can try it at <http://cjam.aditsu.net/> for values up to 10000 or so; for larger numbers you should use the [java interpreter](https://sourceforge.net/projects/cjam/). 1000000 runs in about 3 seconds on my laptop.
**Explanation:**
Unfortunately the straightforward solution is too slow, so I'm keeping only the last 7 digits (before the trailing zeros) after each multiplication.
```
1           push 1 on the stack
ri          read a token and convert to integer
{           loop (for I from 0 to N - 1)
    I)      push I and increment
    *       multiply with the previous value (initially 1)
    _Ab     duplicate and convert to array of digits
    W%      reverse array
    {}#     find the position of the first non-zero digit
    A\#     raise 10 to that power
    /       divide, thus removing all trailing zeros
    1e7%    keep the remainder modulo 10000000
}fI         end for loop
A%          get the last digit
```
**Note:** this language is a lot newer than the question.
[Answer]
# Mathematica, 34 bytes
```
Mod[#!/10^IntegerExponent[#!],10]&
```
[Answer]
# [Java (OpenJDK 8)](http://openjdk.java.net/), 62 bytes
```
n->{long f=n;for(;n>1||f%10==0;)f=n>1?f*--n:f/10;return f%10;}
```
[Try it online!](https://tio.run/##LU9BboNADLz3FValSNAYipO0abNa@oKecolU9bAlbLQpMQiWKBXh7dSQSLalGdnjmaM5m6iscj7uf4esME0Dn8Zx9wDg2Oe1NVkOuxECFCUfIAuEBw6VUL20VOONdxns4AIaBo7Sbtq0mpUt60BxSternVGidaJCoVP6sE9RxBv7TImqc9/WDOOC6gd106zan0I079Ln0u3hJL6Cra8dH76@wYQ3U6MbL1hDR7jAJa7wBV9xjW/4jpQgEdICaYm06tV4MF2JL5iCuI0PJ2b71/j8FJetjyt54QsOHMzhEXQqYw6XWJKH99j98A8 "Java (OpenJDK 8) – Try It Online")
Similar to @Kevin Cruijssen but saves 5 bytes by combining the loops.
[Answer]
# C, ~~150~~ ~~140~~ 135 bytes
```
r,d;f(k,x){r=x<5?3:f(k+1,x/5);return(d=x%5)?r*"33436"[d]*(1<<d*k%4)%5:r;}main(int c,char**v){c=atoi(*++v);printf("%d",c<2?1:2*f(0,c));}
```
This is the version for ASCII systems; replace the string `33436` with `11214` for an EBCDIC system, or with `\1\1\2\1\4` for a portable program.
C solutions are a bit hampered by the requirement to provide a full program; however, this does answer the question fully.
Try it online (requires Javascript):
* [1000000 only](https://tio.run/##HcnRCoIwFIDhV4nB4Jy5yLnWhZv4INGFnGWJZHEwGYjPvqT/7uOn44MoZ9bR9zDqhCs3KbjW1jsLo9PJoef7/OUJYpOkw5aVsPZsL@IabwpMCFGN8ozS1ey3VzdMMEzzgTQ9O1ZqwZWabn4PoIpiQf/h/fYgZBSaQtWaulI9lJoQ/ZZzNuW/Hw "C (gcc) – Try It Online")
* [Loop with all testcases](https://tio.run/##VUztboMwDPzPU1hMSEnINsJHt0EoD9L1B0tKG7ULU0YnpIpn9wLtVM2yffbd2epxrxSi47rqyJGP9OLqURZNVvo1Fnx8LmjldsPZWaLrMSpo41iYZXm2Cjd6y4iQUrNjlNOoKF014YOx6nTWO5Dfgzb902Ed/KNO5mPmPltjibEDtG6vOKhD6xiblx8aXALw0fUOFoeBGkQFHuXi9mMcGwpX2xKzzdbt0Bsyv9iYLa3u6pfzekfCSEO9hki/25CD9SnTRpQp60jCLb1dTMGEKDDFDHMscIUv@IpvKBKfS13brf9B8gs "C (gcc) – Try It Online")
## Explanation
It's based on the algorithm outlined in [Least Significant Non-Zero Digit of n!](http://www.mathpages.com/home/kmath489.htm), turned around so that we recurse in to find the highest power of five, and do the calculation on the way out. The tables of constants were too big, so I reduced them by finding a relationship between the previous residue `r`, the current digit `d` and the recursion depth `k`:
| r | d=0 | d=1 | d=2 | d=3 | d=4 |
| --- | --- | --- | --- | --- | --- |
| 0 | 0 | 3×2^k | 1×2^2k | 3×2^3k | 2 |
| 1 | 1 | 1×2^k | 2×2^2k | 1×2^3k | 4 |
| 2 | 2 | 2×2^k | 4×2^2k | 2×2^3k | 3 |
| 3 | 3 | 3×2^k | 3×2^2k | 3×2^3k | 2 |
| 4 | 4 | 4×2^k | 4×2^2k | 4×2^3k | 1 |
For `r>0`, this resolves to a constant times `r` times `2^dk` (mod 5); the constants are in `a[]` below (inlined in the golfed code). We also observe that `(2^4)%5` is 1, so we can reduce the exponent to avoid overflowing the range of `int`.
```
const int a[] = { 1, 1, 2, 1, 4 };
int f(int k, int x)
{
    int r = x<5 ? 3 : f(k+1,x/5); /* residue - from recursing to higher-order quinary digits */
    int d = x%5;
    if (!d)
        return r;
    return r * a[d] * (1 << d*k%4) % 5;
}
int main(int c, char **v)
{
    c = atoi(*++v);
    printf("%d",
           c<2
           ? 1                  /* special-case 0 & 1 */
           : 2*f(0,c));         /* otherwise, it's 2 times r */
}
```
## Tests:
```
$ for i in 100 1000 10000 100000; do echo $i: `./694 $i`; done
100: 4
1000: 2
10000: 8
100000: 6
1000000: 4
```
Performance is respectable, too. Here's a maximum input for a system with 32-bit `int`:
```
$ time ./694 2147483647
8
real    0m0.001s
user    0m0.000s
sys     0m0.000s
```
I got the same timings with a maximal 64-bit `int`, too.
[Answer]
# PHP - 105
```
 <?foreach(explode("\n",`cat`)as$n)if($n){$f=rtrim(gmp_strval(gmp_fact($n)),'0');echo substr($f,-1)."\n";}
```
Runs under 10 seconds with the given testcase.
[Answer]
## Python3
 **239 Chars**
Can do [10000](http://www.ideone.com/xLq4n) in ~3.2 seconds (Ideone cuts me off at 8 seconds, i'm sure it'll take longer than 10secs though :( )
```
from functools import *
N=100
r=range
s=(p for p in r(2,N)if all(p%n>0for n in r(2,p)))
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=list([p,f(N,p)]for p in s)
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:x[0]**x[1],e))%10)
```
## Python2.6
 **299 Chars** (a bit faster)
```
from itertools import *
N=100000
r=xrange
def s(c=count(2)):
        while 1:p=c.next();c=ifilter(p.__rmod__,c);yield p
f=lambda n,x:n//x+(n//x>0and f(n//x,x)or 0)
e=[[p,f(N,p)]for p in takewhile(lambda x:x<N,s())]
e[0][1]-=e[2][1]
e[2][1]=0
print(reduce(lambda x,y:x*y,map(lambda x:pow(x[0],x[1],10),e))%10)
```
[Answer]
## Haskell, 78 characters
```
f n=head$dropWhile(=='0')$reverse$show$product[1..n]
main=interact(show.f.read)
```
(Would probably need to be compiled to compute 1,000,000! in 10 secs).
[Answer]
## J – ~~42~~ 40 characters
A whole program. Save this program in a file and run with `jconsole script.ijs 1234`. Notice that this program does not exit the interpreter after printing a result. Type `^D` or `exit]0` to exit the interpreter.
```
echo([:{:@(#~*)10&#.inv@*)/1+i.".>{:ARGV
```
Here is an explanation:
* `x #. y` interprets the integer vector `y` as a base `x` number; for example, `10 #. 1 2 3 4` yields `1234`.
* `u inv` yields the *inverse* of a verb `u`. In particular, `x #. inv y` represents `y` as a base `x` number; for example, `10 #. 1234` yields `1 2 3 4`. Notice that `inv` is defined as `^:_1`, that is, `u` applied -1 time.
* `x * y` is the *product* of `x` and `y`, thus `x 10&#.inv@* y` yields a base-10 representation of the product of `x` and `y`.
* `x # y` copies the *n*-th item of `y` as often as the *n*-th item of `x`; when `x` is a vector of booleans, `x` selects which items of `y` to take. For instance, `1 0 1 0 # 1 2 3 4` yields `1 3`.
* `* y` yields the *signum* of `y`.
* `x u~ y` is the *reflexive* of `u`, that is, the same as `y u x`.
* Thus, `y #~ * y` yields a vector of all items of `y` that are positive. In tacit notation, this can written with a *hook* as `(#~ *)`.
* `{: y` yields the last item in `y`.
* assembled together, we get the tacit phrase `([:{:@(#~*)10&#.inv@*)`.
* `u/ y` is the *reduction* of `y`, that is, the dyadic verb `u` inserted between elements of `y`. For instance, `+/1 2 3 4` is like `1 + 2 + 3 + 4` and yields `10`.
* Thus, the phrase `([:{:@(#~*)10&#.inv@*)/ y` yields the last digit of the product of the items of `y`.
* `ARGV` is a boxed vector of the command line arguments.
* `".>{:ARGV` is the last argument unboxed and interpreted as a number.
* `i. y` computes natural numbers from `0` to `y - 1`.
* Thus, `1+i. y` yields natural numbers from `1` to `y`. I could have also used `>:` *increment* here, but `1+` is clearer at the same cost of characters.
* The entire program just applies `1+i.".>{:ARGV` (the vector of `1` to the number in the last command line argument) to the verb `([:{:@(#~*)10&#.inv@*)/` and prints the result with `echo`.
[Answer]
# [Perl 6](https://perl6.org), ~~26~~ 35 bytes
```
{[*](1..$_)~~/.*<(<-[0]>/}
```
[Try it](https://tio.run/##K0gtyjH7X1qcqlBmppdszZVbqaCWnJ@SqmD7vzpaK1bDUE9PJV6zrk5fT8tGw0Y32iDWTr/2f1p@kQJQxtBEoZpLQaE4sVJBSSVewdZOQSVeD6xdQ1OJq/Y/AA "Perl 6 – Try It Online")
---
As a full program:
```
put [*](1..@*ARGS[0])~~/.*<(<-[0]>/
```
[Try it](https://tio.run/##K0gtyjH7X1qcqlBmppdszcVVXJqkkJyfkqqgoaDtoOUY5B6soKlQzaWgAJIoKC1R0FCJBwqoxNf@B/GitWI1DPX0ICqjDWI16@r09bRsNGx0gRw7/f@1XGn5RQpAFYYmYFNAepRU4hVs7RRU4vXUQDZpaCpx1f4HAA "Perl 6 – Try It Online")
## Expanded:
```
{
  [*]( 1..$_ ) # reduce using &infix:« * »
  ~~           # match with
  /
    .*         # any number of values (so it matches from the end)
    <(         # only capture the following
    <-[0]>     # any value but 0 (negated character class)
  /
}
```
[Answer]
# [C (gcc)](https://gcc.gnu.org/), 72 bytes (function)
```
f(n,d)long long n,d;{for(d=1;n;d%=10000)for(d*=n--;d%10<1;d/=10);d%=10;}
```
[Try it online!](https://tio.run/##VY7PCsIwDMbP9inKoNDKiqv/pdYn8SILK4OayRAvY89es@XgzCG/L19CktrGus650ViCSR1GOSeq/NB0vYbgPHpQwVUUZrbWAa0lz1VX52FDLcMTfsyfrgUZ9WKTEYNYvfoW340uVEogw00quGNR0hlJl43xYhTi@WhRz9NRO7IIW8aOsWccGEfGiXFmXBjTR8yfWKil/NNTMeYv "C (gcc) – Try It Online")
# [C (gcc)](https://gcc.gnu.org/), ~~101~~ 99 bytes (whole program)
```
main(){long long n,d=1;for(scanf("%lld",&n);n;d%=10000)for(d*=n--;d%10<1;d/=10);printf("%d",d%10);}
```
[Try it online!](https://tio.run/##HYtBCoAgEEWvEoHhhJKuJw8jDkVgY1i76Oym/sVb/McLeg@hlNMfLOGNifehgxU5i1vK8g6eNzmKGGlUEwMyknDW1EHzNDvWun7WrBZpqQrwygc/rapNM4BfKb0x5gc "C (gcc) – Try It Online")
This question is just shy of 8 years old so "reasonable machine" is not the same as back then, but I'm getting times of ~.01 seconds on my computer when doing all test cases together, so unless computers have increased in speed by a factor of 1000 this last decade, it should be fine.
[Answer]
# [Attache](https://github.com/ConorOBrien-Foxx/Attache), 64 bytes
```
{k.=Floor[_/5]If[_<2,1,6*Digits@$`U1sTny@(_%10)*3^(k%4)*$@k%10]}
```
[Try it online!](https://tio.run/##SywpSUzOSP2fqGBl@786W8/WLSc/vyg6Xt801jMtOt7GSMdQx0zLJTM9s6TYQSUh1LA4JK/SQSNe1dBAU8s4TiNb1URTS8UhG8iPrf3vl5qaUhytUlCQnB7LFVCUmVcSklpc4pxYnFocnaijYGhlqaCuoGFoEGdoZaYZ@x8A "Attache – Try It Online")
Simple implementation of the OEIS formula. `Digits@$`U1sTny` compresses the hardcoded dictionary using Attache's compressed number feature. `$` refers to the function itself within this answer.
[Answer]
# [AWK](https://www.gnu.org/software/gawk/manual/gawk.html), ~~47~~ 57 bytes
```
{for(p=$1;--$1;p=(p*$1)%1e4)while(!(p%10))p/=10;$0=p%10}1
```
[Try it online!](https://tio.run/##bYzBCsIwEETv@YoKKSRCcSeNaaXEf/FQURQMXnqQfnvssgtevOybmR3msjxq/Vxfb1eyxdR12ynZlb2FbzFHv9zuz9ntXGlB3pdDBk2WMtsVtaLJ5wYmMILpGclERjRHCZNgkHAUd2KMBqSEMsgCevXxf51I1jZB0mD1@6pOqrX9BQ "AWK – Try It Online")
Original solution did not handle "large" input values very well. Could add `-M` to force it to work, but that also requires a lot more processing time.
[Answer]
# [PowerShell Core](https://github.com/PowerShell/PowerShell), 56 bytes
```
($s=1).."$args"|%{$s=+("$(($s%1e5)*$_)".Trim(48))}
$s%10
```
[Try it online!](https://tio.run/##XZFBb4JAEIXP7q/YkNWwLRKwaq2JCUlrj7Yp3owxFEelgULZNbRRfjudXSqhzmnem2/eJLtZWkAuDhDH/TDNoWK72akymZi53LYNFuR7YZy7JzRuTYOZOOm6MOI3bMMNe5lHiTmccF4S5TtVSQjb0xk9kQ4TBTYr/0dISOynKNh/pkJGobB9mWZFIMPDejr1ZZDLBRQmJ6TTYzvqqYtEr2sQB7qfx0EmYEvwAvFMQrEsz3Qt6vKLGFh00Ig7i44bMbTosBGjNjZui/s2NmlPHiw6aYTr/FdOew2l095U@prXzvjKqVM4PdPnNJ8H4aH/8v4BocS3VByTIKRFGXxnaMIW35Zt6kkO4hirmYwSQL@HX6BxPV69@o9HIdOkjlt7dZ4q/xiGIISKamL78HVJbLglZimoyVT1phll/9EdY4n3DQ1io8GSlNUv "PowerShell Core – Try It Online")
Naive implementation, takes under 5 seconds on my local, 25 seconds on TIO  
I'll rework it when I get a chance
]