将给定数字的所有因子标记为非素数的算法（尽管它们是素数）

Question

我一整天都在尝试解决 this problem，但我一次又一次地得到 "time limit exceeded"。

我的任务：给定数字 N，我必须排除 [2; 之间的所有质数； N]是这个范围[2;之间的其他数的因数； N].

这是我的代码：

public class Main {

    public static final int SIEVE_LIMIT = 10000001;

    public static final boolean[] COMPOSITES = new boolean[SIEVE_LIMIT];

    private static final ArrayList<Integer> PRIMES = new ArrayList<Integer>();

    public static void main (String[] args) throws NumberFormatException, IOException {

        BufferedReader inStream = null;
        BufferedWriter outStream = null;
        int numCases, curNum, counter;
        StringBuilder resultBuilder = new StringBuilder();
        boolean []temporary = null;

        COMPOSITES[0] = true;
        COMPOSITES[1] = true;

        for(int i = 2; i*i < SIEVE_LIMIT; i++){
            if(!COMPOSITES[i])
                for(int j = i*i; j < SIEVE_LIMIT; j+=i) {
                    COMPOSITES[j] = true;
            }
        }

        for (int i = 2; i < SIEVE_LIMIT; i++) {
          if (!COMPOSITES[i]) 
              PRIMES.add(i);
        }

        inStream = new BufferedReader(new InputStreamReader(System.in));
        outStream = new BufferedWriter(new OutputStreamWriter(System.out));

        numCases = Integer.parseInt(inStream.readLine());

        for(int i = 0; i < numCases; i++){

            curNum = Integer.parseInt(inStream.readLine());
            counter = 0;                        
            temporary = new boolean[SIEVE_LIMIT];

            **// I can't improve this part of the code**
            for(int j = curNum; j > (int) Math.ceil(Math.sqrt(curNum)); j--){

                if(!temporary[j]){
                    for(int aPrime: PRIMES){

                    if(aPrime > (int) Math.ceil(Math.sqrt(j))) break;

                    if(temporary[aPrime]) break;

                    if (j % aPrime == 0) {
                        temporary[aPrime] = true;

                    }                   
                }
            }
        }

        for(int j = 2; j <= curNum; j++) {
            if(!temporary[j] && !COMPOSITES[j])
            counter++;
        }
        //......

        resultBuilder.append(Integer.toString(counter) + '\n');         
    }

      inStream.close();
      outStream.write(resultBuilder.toString().trim() + '\n');
      outStream.close();   
    }
}

如何编写快速-运行代码来解决这个问题。

Answer 1

提示 1

我认为你需要用更数学的方法来解决这个问题。

提示 2

您想要的数字有哪些属性？

提示 3

你知道目标数 x 是质数，而且它不是任何数 y<=n 的因数。

考虑 y=2*x。 x 是一个因素，所以如果 2*x<=n，我们知道 x 不是我们的目标数字之一。

提示 4

尝试找到一种快速计算所有素数 p 的方法，使得 p<=n 且 2*p > n。

将给定数字的所有因子标记为非素数的算法（尽管它们是素数）

Algorithm to mark all factors of a given number as not prime (they are prime numbers though)

algorithm

math

primes

dynamic-programming

number-theory

提示 1

提示 2

提示 3

提示 4