C#,史密斯数(Smith Number)的计算方法与源代码

发布时间:2024年01月14日

一、关于史密斯数的传说

1、关于理海大学Lehigh University

理海大学(Lehigh University),位于宾夕法尼亚州(Pennsylvania)伯利恒(Bethlehem),由富有爱国情怀与民族精神的实业家艾萨·帕克(Asa Packer)创校于1865年,是美国一所历史悠久的私立研究型院校。

2、数学家Albert Wilansky的姐夫H.Smith

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
?

文章来源:https://blog.csdn.net/beijinghorn/article/details/124055190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。