理海大学(Lehigh University),位于宾夕法尼亚州(Pennsylvania)伯利恒(Bethlehem),由富有爱国情怀与民族精神的实业家艾萨·帕克(Asa Packer)创校于1865年,是美国一所历史悠久的私立研究型院校。
1982年,Lehigh大学的数学家Albert Wilansky在查看电话簿的时候,突然发现他的姐夫H.Smith的电话号码有一个很特别的性质:
该数字的所有位数之和,等于该数所有质因子的位数之和!
4937775 = 3 * 5 * 5* 65837
4937775的位数和为:
4+9+3+7+7+7+5 = 42
而该数所有质因子的位数之和为:
3+5+5+(6+5+8+3+7) = 42
于是Albert Wilansky将有这种性质的数叫做Smith number。
很显然,质数都有这种性质,所以他把质数排除在外。
运行效果:
输入一个数,求出其质因子的位数之和,然后判断是否和原数的位数之和相等,质数排除在外,因为任何一个数(大于2的数)除了质数都可以写成一系列的从小的大的质数的乘的形式,所以对于每一个数都做这样的计算,从i(i>=2)开始遍历,如果这个数对i取摸等于0,那么将这个数除以i,直到取摸i不等于0,纪录i的个数,然后在计算一个i的位数之和,总的位数和为(个数*一个的位数之和),然后i++,i的上界为sqrt(n+0.0),当然最后还要做一个判断,这个数是否是质数,这可以在循环中加一个标记来判断是否有因子;如果是质数,最后n是否是1,如果不是加上这个数的位数之和,否则跳过。
其中涉及到 质数的?Sundaram筛选法,也叫“森德拉姆素数筛法”。
using System;
using System.Collections;
using System.Collections.Generic;
namespace Legalsoft.Truffer.Algorithm
{
public static class SmithNumber
{
/// <summary>
/// 最大数
/// </summary>
public static int MAX { get; set; } = Int32.MaxValue - 1024;
/// <summary>
/// 质数数组
/// </summary>
public static List<int> primes { get; set; } = new List<int>();
/// <summary>
/// 质数序列计算的 Sundaram 算法
/// Sundaram筛选法,也叫“森德拉姆素数筛法”
/// </summary>
public static void SieveSundaram()
{
bool[] marked = new bool[MAX];
for (int i = 1; i <= (Math.Sqrt(MAX) - 1) / 2; i++)
{
for (int j = (i * (i + 1)) << 1; j <= MAX / 2; j = j + 2 * i + 1)
{
marked[j] = true;
}
}
primes.Add(2);
for (int i = 1; i <= MAX / 2; i++)
{
if (marked[i] == false)
{
primes.Add(2 * i + 1);
}
}
}
/// <summary>
/// 判断 n 是不是 史密斯数
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public static bool IsSmith(int n)
{
int original_no = n;
int pDigitSum = 0;
for (int i = 0; (int)primes[i] <= n / 2; i++)
{
while (n % (int)primes[i] == 0)
{
int p = (int)primes[i];
n = n / p;
while (p > 0)
{
pDigitSum += (p % 10);
p = p / 10;
}
}
}
if (n != 1 && n != original_no)
{
while (n > 0)
{
pDigitSum = pDigitSum + n % 10;
n = n / 10;
}
}
int sumDigits = 0;
while (original_no > 0)
{
sumDigits = sumDigits + original_no % 10;
original_no = original_no / 10;
}
return (pDigitSum == sumDigits);
}
}
}
---------------------------------------
POWER BY TRUFFER.CN
?