### Repunit nonfactors题号：133 难度： 50 中英对照

A number consisting entirely of ones is called a repunit. We shall define R(k) to be a repunit of length k; for example, R(6) = 111111.

Let us consider repunits of the form R(10n).

Although R(10), R(100), or R(1000) are not divisible by 17, R(10000) is divisible by 17. Yet there is no value of n for which R(10n) will divide by 19. In fact, it is remarkable that 11, 17, 41, and 73 are the only four primes below one-hundred that can be a factor of R(10n).

Find the sum of all the primes below one-hundred thousand that will never be a factor of R(10n).

### Code

import java.math.BigInteger;

public final class p133 {
public static void main(String[] args) {
long start=System.nanoTime();
String result = run();
long end=System.nanoTime();
System.out.println(result);
System.out.println( (end-start)/1000000 + "ms" );
}
static public String run(){
long sum = 0;
for (int i = 2; i <= 100000; i++) {
if (!isPrime(i)) continue;
if (i == 2 || i == 5 || !hasDivisibleRepunit(i))
sum += i;
}
return Long.toString(sum);
}

private static final BigInteger EXPONENT = BigInteger.TEN.pow(16);

// Tests whether there exists a k such that R(10^k) is a multiple of p
private static boolean hasDivisibleRepunit(int p) {
return (BigInteger.TEN.modPow(EXPONENT, BigInteger.valueOf(p * 9)).intValue() - 1) / 9 % p == 0;
}

static private boolean isPrime(int i){
if(i<=1) return false;
if(i==2) return true;
if((i&1)==0) return false;
for(int j=3;j<=i/j;j++)
if(i%j==0) return false;
return true;
}
}
453647705
161ms