如何求出1-1000的质素 （不能用除法和求余）

Question

第一题如题
第二题 如何将0-1之间的数开平方（不能用Math函数）

Answer 1

第一题:package prime.v3;public class PrimeGenerator {    public static int[] generatePrimes(int maxValue) {
        if (maxValue < 2)
            return new int[0];
        else {
            boolean[] crossedOut = uncrossIntegersUpTo(maxValue);
            crossOutMultiples(crossedOut);
            return putUncrossedIntegerIntoResult(crossedOut);
        }
    }    private static int[] putUncrossedIntegerIntoResult(boolean[] crossedOut) {
        int[] result = new int[numberOfUncrossedInteger(crossedOut)];
        for (int i = 0, j = 0; i < crossedOut.length; i++) {
            if (!crossedOut[i])
                result[j++] = i;
        }
        return result;
    }    private static int numberOfUncrossedInteger(boolean[] crossedOut) {
        int count = 0;
        for (int i = 0; i < crossedOut.length; i++) {
            if (!crossedOut[i])
                count++;
        }
        return count;
    }    private static boolean[] uncrossIntegersUpTo(int maxValue) {
        boolean[] crossedOut = new boolean[maxValue + 1];
        crossedOut[0] = crossedOut[1] = true;
        for (int i = 2; i < crossedOut.length; i++)
            crossedOut[i] = false;
        return crossedOut;
    }    private static void crossOutMultiples(boolean[] crossedOut) {
        int limit = (int) Math.sqrt(crossedOut.length);
        for (int i = 2; i <= limit; i++) {
            if (!crossedOut[i])
                crossOutMultiplesOf(i, crossedOut);
        }
    }    private static void crossOutMultiplesOf(int i, boolean[] crossedOut) {
        for (int multiple = 2 * i; multiple < crossedOut.length; multiple += i) {
            crossedOut[multiple] = true;
        }
    }    public static void main(String[] args) {
        int[] primes = generatePrimes(100);
        for (int prime : primes)
            System.out.println(prime);
    }}

Answer 2

1、如果允许开辟1000大小的数组，那么只要 boolean[] array = new boolean[1001];
for (int i = 0; i < array.length; i++)
array[i] = true;
for(int i = 2; i < array.length; i++) {
if(array[i]) {
int index = i * 2;
while(index <= 1000) {
array[index] = false;
index += i;
}
}
}
for(int i = 2; i < array.length; i++) {
if(array[i])
System.out.println(i);
}
2、这个可以用折半查找之类的方法 double x = 0.3;
double a = 0;
double b = 1; while(true) {
double c = (a + b) / 2;
double diff = c * c - x;
if(diff == 0) {
System.out.println(c);
return;
}
if(a == c || b == c) {
System.out.println(c);
return;
}
if(diff > 0)
b = c;
else
a = c;
}

Answer 3

public void prime(int m , int n){

for (int i = m; i <= n; i++) {
boolean flag = true;
for(int j = 2; j < i; j++){
if(i % j == 0){
flag = false;
break;
}
}
if(flag){
System.out.println(i);
}
}
}

Answer 4

再回一次：第二题：
设Y=√X
Yn+1 = (Yn + X/Yn)/2double X, Y;double e = 0.000001; //误差
//输入X
Y=X;
double temp=(Y+X/Y)/2;
while(abs(Y - temp) > e){
  temp = Y;
  Y = (Y+X/Y)/2;
}
System.out.println("Y="+Y);大概写的，没运行过，反正就是这么个公式