Java程序打印出可被其他数字整除的数字

Question

我有一个程序，它读取两个实数，然后打印出这两个数字之间的所有数字，这些数字可以被 2 或 3 或 5 整除。该程序工作正常，但是当用户输入两个非常大的数字时(例如例如，1122222123333 和 214123324434434) 程序需要很长时间来计算结果。我想以某种方式修复该程序，以便即使对于大量数据，结果也会立即打印出来。

这是我到目前为止的代码:

import java.util.Scanner;
public class Numbers 
{
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);        
        long x = sc.nextLong();   // first number input 
        long y = sc.nextLong();   // second number input            
        long num = 0;            // new variable num -- means all the numbers between these to given input numbers
        long count = 0;            // loop counter - how many numbers are divided by 2 or 3 or 5                        
        for (num = x; x <= num && num <= y; num++) {                                                    
            if (num % 2 == 0 | num % 3 == 0 | num % 5 == 0) {
                count = count + 1;             // increasing the counter by 1, so that every time the loop repeats, the counter increases...                                
            }               
        }
        System.out.println(count);  // prints out how many numbers are divided by 2 or 3 or 5 ...       
    }
}

Answer 1

好吧，你根本不需要循环。

1. 您知道 x 和 y 之间能被 2 整除的数字的个数是 (y-x)/2(加减一)。

2. 同样，x 和 y 之间能被 3 整除的数字的个数为 (y-x)/3(加减一)。

3. x 和 y 之间能被 5 整除的数字个数为 (y-x)/5(加减一)。

您只需删除多次数过的数字即可。

如果您考虑 A、B 和 C 组，即分别能被 2、3 和 5(在要求的范围内)整除的数字组，您的目标是找到:

|A 联合 B 联合 C| =|A| + |B| + |C| - |A 与 B 的交集| - |与 C 的交集| - |B 与 C 的交集| + |A 与 B 的交集与 C| 的交集

因此，你必须减去能被2*3整除的数字、能被2*5整除的数字和能被3*5整除的数字。最后，您必须添加能被 2*3*5 整除的数字。

示例:

在 1000 和 2000 之间，大约有 (2000-1000)/2 = 500 个能被 2 整除的数字:1000,1002,1004,...,2000。实际上，计数减少了 1，因为它是 501 而不是 500，但您可以通过添加一些检查范围边缘的逻辑来对此进行调整。

类似地，大约有 (2000-1000)/3 = 333 个数字可以被 3 整除:1002, 1005, 1008, ..., 1998。

大约 (2000-1000)/5 = 200 个能被 5 整除的数字:1000,1005,1010,...,2000。这里计数又减一了。