英文:
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 < 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);
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).&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 < 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);
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.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论