### Large repunit factors题号：132 难度： 45 中英对照

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(10) = 1111111111 = 11×41×271×9091, and the sum of these prime factors is 9414.

Find the sum of the first forty prime factors of R(109).

### Code

import java.io.BufferedReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;

public final class p132 {
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(){
int sum = 0;
int count = 0;
for (int i = 2; count < 40; i++) {
if (isPrime(i) && repunitMod(1000000000, i) == 0) {
sum += i;
count++;
}
}
return Integer.toString(sum);
}

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;
}

private static int repunitMod(int k, int m) {
return (power(10, k, m * 9) - 1) / 9;
}

static int power(int x,int y,int m){
int z = 1;
while (y != 0) {
if ((y & 1) != 0)
z = (int)((long)z * x % m);
x = (int)((long)x * x % m);
y >>>= 1;
}
return z;
}
}
843296
46ms