从1到100,000的亲和数之和 (AP CS-A)

huangapple go评论72阅读模式
英文:

Sum of amicable numbers from 1-100,000 (AP CS-A)

问题

我们今天课堂上的任务是找出在1-100000范围内所有亲和数的和。

int sum = 0;
for (int i = 1; i < 100000; i++) {
    int a = 1;
    for (int j = 2; j <= Math.sqrt(i); j++) {
        if (i % j == 0) {
            if (j == (i / j))
                a += j;
            else
                a += (j + i / j);
        }
    }

    int b = 1;
    for (int j = 2; j <= Math.sqrt(a); j++) {
        if (a % j == 0) {
            if (j == (a / j))
                b += j;
            else
                b += (j + a / j);
        }
    }
    if (a == b) sum += a;
}

System.out.println(sum);

这是我今天在课堂上写的代码。不幸的是,它没有起作用,现在变成了作业。

亲和数的定义见:https://en.wikipedia.org/wiki/Amicable_numbers#:~:text=Amicable%20numbers%20are%20two%20different,is%20(220%2C%20284).&text=For%20example%2C%20the%20proper%20divisors%2C%20aliquot%20sequence%20of%20period%202.

我需要在不使用辅助方法且不重复计算可能性的情况下完成这个目标,但是不知何故,我一直得到错误的答案。不幸的是,我们只能使用数组和ArrayList作为数据结构,以保持简单。

英文:

Our task in class today was to find the sum of all amicable numbers from 1-100000.

 int sum = 0;
        for(int i = 1; i &lt; 100000; i++ ) {
            int a = 1;
            for (int j = 2; j &lt;= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    if (j == (i / j))
                        a += j;
                    else
                        a += (j + i / j);
                }
            }

            int b = 1;
            for (int j = 2; j &lt;= Math.sqrt(a); j++) {
                if (a % j == 0) {
                    if (j == (a / j))
                        b += j;
                    else
                        b += (j + a / j);
                }
            }
            if(a==b) sum += a;
        }
        
        System.out.println(sum);

This is the code I made in class today. Unfortunately it did not work and not it's homework.

Amicable numbers are defined by: https://en.wikipedia.org/wiki/Amicable_numbers#:~:text=Amicable%20numbers%20are%20two%20different,is%20(220%2C%20284).&amp;text=For%20example%2C%20the%20proper%20divisors,aliquot%20sequence%20of%20period%202.

I need to accomplish this goal without using helper methods and not double counting possibilities, but I somehow keep getting wrong answers. Unfortunately, we can only use arrays and ArrayList for data structures to keep it simple.

答案1

得分: 2

你可以使用一个布尔数组来跟踪你已经计数过的值。以下是一个可行的解决方案:

boolean[] arr = new boolean[100000];
for (int i = 1; i < 100000; i++) {
    int a = 1;
    for (int j = 2; j <= Math.sqrt(i); j++) {
        if (i % j == 0) {
            if (j == (i / j))
                a += j;
            else
                a += (j + i / j);
        }
    }

    int b = 1;
    for (int j = 2; j <= Math.sqrt(a); j++) {
        if (a % j == 0) {
            if (j == (a / j))
                b += j;
            else
                b += (j + a / j);
        }
    }

    if (i == b && i != a) {
        if (!arr[i])
            arr[i] = true;
        if (!arr[b])
            arr[b] = true;
    }
}

int sum = 0;
for (int i = 0; i < arr.length; i++) {
    if (arr[i] == true) {
        sum += i;
    }
}
System.out.println(sum);

要使此代码适用于1到n的数字范围,你可以将数组长度和for循环中的100000替换为方法参数。

英文:

You can use a boolean array to keep track of which values you already counted. Here is a working solution:

		boolean[] arr = new boolean[100000];
		for(int i = 1; i &lt; 100000; i++ ) {
			int a = 1;
			for (int j = 2; j &lt;= Math.sqrt(i); j++) {
				if (i % j == 0) {
					if (j == (i / j))
						a += j;
					else
						a += (j + i / j);
				}
			}

			int b = 1;
			for (int j = 2; j &lt;= Math.sqrt(a); j++) {
				if (a % j == 0) {
					if (j == (a / j))
						b += j;
					else
						b += (j + a / j);
				}
			}

			if(i == b &amp;&amp; i != a) {
				if(!arr[i])
					arr[i] = true;
				if(!arr[b])
					arr[b] = true;
			}
		}

		int sum = 0;
		for(int i = 0; i &lt; arr.length; i++) {
			if(arr[i] == true) {
				sum += i;
			}
		}
		System.out.println(sum);

To make this work for numbers 1 to n you can replace the array length and the 100000 in the for loop with a method parameter.

huangapple
  • 本文由 发表于 2020年9月10日 06:44:54
  • 转载请务必保留本文链接:https://go.coder-hub.com/63820505.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定