在给定范围之间找到史密斯数

Question

我会很快进入正题。基本上史密斯数是：合数，其数字之和是其素因数(不包括1(的位数之和。(素数被排除在外，因为它们微不足道地满足这个条件(。史密斯数的一个例子是野兽数 666=2·3·3·37，因为 6+6+6=2+3+3+(3+7(=18。

我尝试过什么：

1. 首先在 for 循环中，我得到当前数字 (i( 位的总和
2. 在同一个循环中，我尝试获取数字的素因数数字的总和。
3. 我制作了另一种方法来检查将要进入for循环的当前数字是否是素数，如果其素数将被排除

但是我的代码似乎不起作用，你们可以帮忙吗？

public static void main(String[] args) {
smithInrange(1, 50);
}
public static void smithInrange(int start_val, int end_val) {
for (int i = start_val; i < end_val; i++) {
if(!isPrime(i)) { //since we banned prime numbers from this process i don't include them 
int for_digit_sum = i, digit = 0, digit_sum = 0, for_factor_purpose = i, smith_sum = 0;
int first = 0, second = 0, last = 0;
// System.out.println("current number is" + i);
while (for_digit_sum > 0) { // in this while loop i get the sum of current number's digits
digit = for_digit_sum % 10;
digit_sum += digit;
for_digit_sum /= 10;
}
// System.out.println("digit sum is"+digit_sum);
while (for_factor_purpose % 2 == 0) { // i divide the current number to 2 until it became an odd number
first += 2;
for_factor_purpose /= 2;
}
// System.out.println("the first sum is " + first);
for (int j = 3; j < Math.sqrt(for_factor_purpose); j += 2) {
while (for_factor_purpose % j == 0) { // this while loop is for getting the digit sum of every prime
// factor that j has
int inner_digit = 0, inner_temp = j, inner_digit_sum = 0;
while (inner_temp > 0) {
inner_digit = inner_temp % 10;
second += inner_digit;
inner_temp /= 10;
}
// System.out.println("the second sum is " + second);
for_factor_purpose /= j;
}
}
int last_temp = for_factor_purpose, last_digit = 0, last_digit_sum = 0;
if (for_factor_purpose > 2) {
while (last_temp > 0) {
last_digit = last_temp % 10;
last += last_digit;
last_temp /= 10;
}
// System.out.println("last is " + last);
}
smith_sum = first + second + last;
// System.out.println("smith num is "+ smith_sum);
// System.out.println(smith_sum);
if (smith_sum == digit_sum) {
System.out.println("the num founded is" + i);
}
}
}
}
public static boolean isPrime(int i) {
int sqrt = (int) Math.sqrt(i) + 1;
for (int k = 2; k < sqrt; k++) {
if (i % k == 0) {
// number is perfectly divisible - no prime
return false;
}
}
return true;
}

输出为： NUM 成立 IS4 NUM 成立 IS9 NUM 成立 IS22 NUM 成立 IS25 NUM 成立 IS27 NUM 成立 IS49

这个范围(1 到 50(之间的史密斯数是如何的： 4、22 和 27

编辑：I_ve发现了问题： Math.sqrt(for_factor_purpose( 似乎我应该加 1 来消除平方数。多亏了你们，我看到了其他角度的解决方案。 继续编码！

Answer 1

用于打印史密斯数字的主循环。

for (int i = 3; i < 10000; i++) {
if (isSmith(i)) {
System.out.println(i + " is a Smith number.");
}
}

确定所提供的数字是否为史密斯数的测试方法。 仅当最后一个素数的量级小于被测数时，素数列表才会增加。

static boolean isSmith(int v) {
int sum = 0;
int save = v;
int lastPrime = primes.get(primes.size() - 1);
if (lastPrime < v) {
genPrimes(v);
}
outer:
for (int p : primes) {
while (save > 1) {
if (save % p != 0) {
continue outer;
}
sum += sumOfDigits(p);
save /= p;
}
break;
}
return sum == sumOfDigits(v) && !primes.contains(v);
}

对数字的数字求和的帮助程序方法。

static int sumOfDigits(int i) {
return String.valueOf(i).chars().map(c -> c - '0').sum();
}

和主发电机。 它在创建时使用该列表来确定是否给定 数字是一个素数。

static List<Integer> primes = new ArrayList<>(List.of(2, 3));
static void genPrimes(int max) {
int next = primes.get(primes.size() - 1);
outer:
while (next <= max) {
next += 2;
for (int p : primes) {
if (next % p == 0) {
continue outer;
}
if (p * p > next) {
break;
}
}
primes.add(next);
}
}
}

Answer 2

我不想破坏答案的发现，而只是一些更简单的代码片段， 让一切更简单，更具可读性。

public boolean isSmith(int a) {
if (a < 2) return false;
int factor = findDivisor(a);
if (factor == a) return false;
int sum = digitSum(a);
// loop:
a /= factor;
sum -= digitSum(factor);
...
}
boolean isPrime(int a){
for(int i = 2; i*i <= a; i++) {
if (a % i == 0) {
return false;
}
}
return true;
}
int findDivisor(int a){
for(int i = 2; i*i <= a; i++) {
if (a % i == 0) {
return i;
}
}
return a;
}
int digitSum(int a) {
if (a < 10) {
return a;
}
int digit = a % 10;
int rest = a / 10;
return digit + digitSum(rest); 
}

如您所见，整数除法 23/10 == 2，而模(余数(%：23 % 10 == 3 可以简化事情。

而不是 isPrime，查找因子更合乎逻辑。事实上，最好的解决方案不是使用查找除数，而是立即找到所有因素

int factorsSum = 0;
int factorsCount = 0;
for(int i = 2; i*i <= a; i++) {
while (a % i == 0) {
factorsSum += digitSum(i);
a /= i;
factorsCount++;
}
}
// The remaining factor >= sqrt(original a) must be a prime.
// (It cannot contain smaller factors.)
factorsSum += digitSum(a);
factorsCount++;

Answer 3

这是代码。如果您需要进一步的帮助，请告诉我。该代码非常不言自明，并且从您的代码中获取了相当多的内容，但如果您需要我解释它，请告诉我。

简而言之，我创建了方法来检查数字是否是史密斯数，然后检查范围中的每个整数。

import java.util.*;
public class MyClass {
public static void main(String args[]) {
System.out.println(smithInRange)
}
public int factor;
public boolean smithInRange(int a, int b){
for (int i=Math.min(a,b);i<=Math.max(a,b);i++) if(isSmith(i)) return true;
return false;
}
public boolean isSmith(int a){
if(a<2) return false;
if(isPrime(a)) return false;
int digits=0;
int factors=0;
String x=a+¨" ";
for(int i=0;i<x.length()-1;i++) digits+= Integer.parseInt(x.substring(i,i+1));
ArrayList<Integer> pF = new ArrayList<Integer>();
pF.add(a);
while(!aIsPrime(pF)){
int num = pF.get(pF.size-1)
pF.remove(pF.size()-1);
pF.add(factor);
pF.add(num/factor)
}
for(int i: pF){
if((factors+"").length()==1)factors+= i;
else{
String ss= i+" ";
int nums=0;
for(int j=0;j<ss.length()-1;j++){
nums+=Integer.parseInt(ss.substring(j,j+1));
}
}
}
return (factors==digits);
}
public boolean isPrime(int a){
for(int i=2;i<=(int)Math.sqrt(a),i++){
String s = (double)a/(double)i+"";
if(s.substring(s.length()-2).equals(".0")){
return false;
factor = i;
}
}
return true;
}
public boolean aIsPrime(ArrayList<int> a){
for(int i: a) if (!isPrime(a)) return false;
return true;
}
}