演習課題「素因数分解を実装する」
整数 n が入力として与えられるので、n を素因数分解したときに現れる素数を小さい方から順に改行区切りで出力してください。同じ素数が複数回現れる場合は、現れる回数だけその素数を出力してください。
右側のコードエリアには、入力 n を受け取り、関数 factorize によって素因数分解をおこない、その結果として現れる素数を小さい方から順に改行区切りで出力するコードが用意されています。関数 factorize のコードを書き加え、コードを完成させてください。
期待する出力値
2
2
2
演習課題「約数の個数を求める」
整数 n が入力として与えられるので、n の約数が何個あるかを求めてください。
右側のコードエリアには、入力 n を受け取り、関数 calcNumOfPrimeFactors によって n の約数の個数を求め、出力するコードが用意されています。関数 calcNumOfPrimeFactors のコードを書き加え、コードを完成させてください。
期待する出力値
9
＃05:素因数分解・約数の個数
このチャプターでは、素因数分解と、約数の個数の求め方について学習します。
import java.util.HashMap;
public class Main {
// 整数を受け取り、素因数分解をおこなって (素因数、個数) の連想配列を返す関数
static HashMap<Integer, Integer> factorize(int n) {
HashMap<Integer, Integer> primes = new HashMap<>();
for (int i = 2; i * i <= n; i++) {
if (n % i > 0) {
continue;
}
int exp = 0;
while (n % i == 0) {
exp++;
n /= i;
}
primes.put(i, exp);
}
if (n != 1) {
primes.put(n, 1);
}
return primes;
}
public static void main(String[] args) {
int n = 813;
HashMap<Integer, Integer> table = factorize(n);
for(int prime : table.keySet()){
int exp = table.get(prime);
for(int i = 0; i < exp; i++){
System.out.println(prime);
}
}
}
}
import java.util.HashMap;
public class Main {
// 整数を受け取り、素因数分解をおこなって (素因数、個数) の連想配列を返す関数
static HashMap<Integer, Integer> factorize(int n) {
HashMap<Integer, Integer> primes = new HashMap<>();
for (int i = 2; i * i <= n; i++) {
if (n % i > 0) {
continue;
}
int exp = 0;
while (n % i == 0) {
exp++;
n /= i;
}
primes.put(i, exp);
}
if (n != 1) {
primes.put(n, 1);
}
return primes;
}
// 整数を受け取り、約数の個数を返す関数
static int calcNumOfPrimeFactors(int n) {
HashMap<Integer, Integer> primes = factorize(n);
int numOfPrimeFactors = 1;
for (int num : primes.values()) {
numOfPrimeFactors *= (num + 1);
}
return numOfPrimeFactors;
}
public static void main(String[] args) {
int n = 813;
int numOfPrimeFactors = calcNumOfPrimeFactors(n);
System.out.println(n + "の約数は" + numOfPrimeFactors + "個");
}
}