日期:2014-05-20 浏览次数:21698 次
using System.Collections.Generic;
using System;
namespace ConsoleApplication1
{
class Program
{
static Dictionary<int, int> dItems = new Dictionary<int, int>(); //存放据有输入数的质因数
static void Main(string[] args)
{
int[] Input = new int[10]; //输入
int n, MaxInput = 0; //当前输入,最大输入
//读入输入
for (int i = 0; i < 10; i++)
{
while (!int.TryParse(Console.ReadLine(), out n) || n <= 0 || n > 10000)
{
Console.WriteLine("该输入无效,请重新输入(需要1-10000的整数)。");
}
Input[i] = n;
if (MaxInput < n)
{
MaxInput = n;
}
}
//求所有程序中可能用到的质数
GetItem(MaxInput);
//分解所有整数
for (int i = 0; i < 10; i++)
{
Split(Input[i]);
}
//计算约数个数
int Count = 1;
foreach (int i in dItems.Values)
{
Count *= 1 + i;
}
Console.WriteLine("英雄编号是:" + Count % 10);
Console.Read();
}
//分解P,表示为 a1^b1+a2^b2+...的形式
private static void Split(int p)
{
if (p == 1)
{
return;
}
if (dItems.ContainsKey(p)) //p是质数
{
dItems[p]++;
return;
}
for (int i = 2; i <= p && p > 1; i++) //找P的质因数
{
if (p % i == 0)
{
dItems[i]++;
p /= i;
i--;
}
}
}
static void GetItem(int Max) //筛选法求素数,网上抄了个c的改了下
{
int[] sieve = new int[Max + 1]; //Max以内的数
//step 1:
//初始化(sieve[i] = 0 表示不在筛中,即不是质数;1表示在筛中)
for (int i = 2; i <= Max; i++) //从2开始,因为0和1不是质数
sieve[i] = 1;
//step 2:
//偶数(2的倍数)肯定不是质数,所以应该先筛除
for (int i = 2; i <= Max / 2; i++)
sieve[i * 2] = 0;
int p = 2; //第一个质数是2
//step 3:从sieve中删去P的倍数
while (p * p <= Max)
{
//选下一个p
p = p + 1;
while (sieve[p] == 0)
p++;
int t = p * p;
int s = 2 * p;
while (t <= Max)
{
sieve[t] = 0; //删除
t = t + s;
}
}
//step 4: 输出结果
for (int i = 2; i <= Max; i++)
{
if (sieve[i] != 0)
{
dItems.Add(i, 0);
}
}
}
}
}