标签: perfect-numbers

我目前正在试验F#.在互联网上找到的文章很有帮助,但作为一名C#程序员,我有时遇到我认为我的解决方案会有所帮助的情况,但它没有或只是部分帮助.

因此,我对F#缺乏了解(最有可能的是,编译器的工作方式)可能是我有时会非常惊讶的原因.

例如,我写了一个C#程序来确定完美的数字.它使用欧几里德证明的已知形式,可以从Mersenne Prime 2p-1(2p-1)(其中2p-1是素数,p表示为幂)形成完美数.

由于F#的帮助声明'**'可用于计算功率,但使用浮点,我试图用bitshift运算符创建一个简单的函数(<<<)(注意我编辑了这个代码指出需要):

 let PowBitShift (y:int32) = 1 <<< y;;

但是,在运行测试并寻找性能改进时,我还尝试了一种形式,我记得使用Miranda(一种函数式编程语言),它使用递归和模式匹配器来计算功率.主要的好处是我可以使用变量y作为64位整数,这对于标准的bitshift运算符是不可能的.

    let rec Pow (x : int64) (y : int64) = 
    match y with
        | 0L -> 1L
        | y -> x * Pow x (y - 1L);;

事实证明,这个功能实际上更快,但我不能(还)理解原因.也许这是一个不那么智力的问题,但我仍然很好奇.

那么秒的问题就是,当计算完美数字时,你会遇到这样一个事实:在找到第9个完美数字(由31的幂形成)之后,int64无法显示大数字交叉.我试图找出你是否可以使用BigInteger对象(或bigint类型),但在这里我对F#的了解阻止了我一点.是否有可能创建一个接受两个参数的幂函数？

我目前有这个:

let rec PowBigInt (x : bigint) (y : bigint) = 
    match y with
        | bigint.Zero -> 1I
        | y -> x * Pow x (y - 1I);;

但它抛出了bigint.Zero未定义的错误.所以我也在做错事.0I不被接受作为替代,因为它给出了这个错误:

Non-primitive numeric literal constants cannot be …

我正在寻找一种算法来查找给定数字是否是完美数字.

我想到的最简单的是:

1. 找到该数字的所有因素
2. 得到主要因素[除了数字本身,如果它是素数]并将它们加起来检查它是否是一个完美的数字.

有一个更好的方法吗 ？.在搜索时,一些欧几里德的工作出现了,但没有找到任何好的算法.这个golfscript也没有帮助:https://stackoverflow.com/questions/3472534/checking-whether-a-number-is-mathematically-a-perfect-number .

数字等可以在实际使用中缓存等[我不知道在哪里使用完美的数据:)]
但是,由于这是在采访中被问到的,我假设应该有一种"可导出"的方式来优化它.

谢谢 !

我一直在努力使用C#代码优化Lucas-Lehmer素性测试(是的,我正在使用Mersenne primes来计算完美数字.我想知道当前代码可以进一步提高速度.我使用System.Numerics.BigInteger类来保存数字,也许它不是最明智的,我们会看到它.

此代码实际上基于以下网站上的智能:http://en.wikipedia.org/wiki/Lucas%E2%80%93Lehmer_primality_test

这个页面(在时间戳)部分,给出了一些证据来优化分割.

LucasTest的代码是:

public bool LucasLehmerTest(int num)
{
  if (num % 2 == 0)
     return num == 2;
  else
  {
     BigInteger ss = new BigInteger(4);
     for (int i = 3; i <= num; i++)
     {
        ss = KaratsubaSquare(ss) - 2;
        ss = LucasLehmerMod(ss, num);
     }
     return ss == BigInteger.Zero;
  }

}

编辑: 这比使用下面的Mare Infinitus建议的BigInteger类中的ModPow更快.该实施是:

public bool LucasLehmerTest(int num)
{
  if (num % 2 == 0)
     return num == 2;
  else
  {
     BigInteger m = …

我在C#中编写了一个程序,以便在一定范围内找到完美的数字,作为编程挑战的一部分.但是,我意识到计算10000以上的完美数字时速度非常慢.有没有找到完美数字的优化方法？我的代码如下:

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleTest
{
 class Program
 {
  public static List<int> FindDivisors(int inputNo)
  {
   List<int> Divisors = new List<int>();
   for (int i = 1; i<inputNo; i++)
   {
    if (inputNo%i==0)
     Divisors.Add(i);
   }
   return Divisors;
  }

  public static void Main(string[] args)
  { 
   const int limit = 100000;

   List<int> PerfectNumbers = new List<int>();
   List<int> Divisors=new List<int>();
   for (int i=1; i<limit; i++)
   {
    Divisors = FindDivisors(i);
    if (i==Divisors.Sum())
     PerfectNumbers.Add(i);
   }

   Console.Write("Output =");

   for (int i=0; i<PerfectNumbers.Count; i++)
   {
    Console.Write(" …

我需要编写一个 C 程序来找到完美数..

main()
{
    int n=1000,sum = 0;
    for(int num = 1; num <= n; num++)
    {
        sum = 0;
        for(int i = 1; i < num; i++)
        {
            if(!(num%i))
            {
                sum+=i;
            }
        }
        if(sum == num)
            printf("\n%d",num);
    }
}

if(!(num%i)) - 这是 d 线我不明白。

如果还有其他简单的方法请推荐我

我每周都会做一次计算机科学实验室的入门课程.我希望在下一个实验结束时能够快速参加比赛.我想给他们一个像这样的代码块:

public class EfficientCode{

    public static void main(){
        long startTime, endTime, executionTime;
        startTime = System.currentTimeMillis();

        yourEfficientMethod():
        endTime = System.currentTimeMillis();
        executionTime = endTime – startTime;

    }

    public static void doSomething(){
        // you do this part.  
    }

}

他们将实施doSomething方法,拥有最快代码的人将获得一些奖励分数.

问题是这个问题需要有点简单.学生可以很好地掌握:循环,if/else,字符串,添加,数组等.

以下是我对问题的看法:

• 找到1到1,000,000之间的所有完美数字.(一个完美的数字是一个数字,其中所有数字的因素加起来就是数字.即:6 = 3 + 2 + 1)
• 找到1到1,000,000之间的所有素数

我认为,为了在方法之间存在可衡量的性能差异,您必须多次执行某些操作.

我在python上做了完美数字的实验室它运行良好并打印了我需要的数字.但不确定我是否需要将(1,1000)放入范围或(2,n + 1)是否正常？我的指示要求我

"编写一个python程序,找到从1到10,000的所有完美数字.当找到一个完美的数字时,你的逻辑应该打印它."

什么是完全数:

在数论中,一个正数是一个正整数,等于其正确的除数之和,即除数自身的正除数之和(也称为等分和).等价地,完美数字是所有正除数(包括其自身)的总和的一半,即σ1(n)= 2n.

当我运行我的程序时,它打印出6,28,496和8128.

 n = 1
 while True:
     factors = [1]
     [factors.append(i) for i in range(2,n+1) if n%i == 0]
     if sum(factors) == 2*n: print n
     n += 1

链接:http://projecteuler.net/problem=23

完美数字是一个数字,其正确除数的总和恰好等于数字.例如,28的适当除数之和为1 + 2 + 4 + 7 + 14 = 28,这意味着28是一个完美数.

如果n的适当除数之和小于n,则数n被称为不足,如果该和超过n,则称其为n.

由于12是最小的有限数,1 + 2 + 3 + 4 + 6 = 16,可以写成两个有限数之和的最小数是24.通过数学分析,可以显示所有整数大于28123可以写成两个数字的总和.然而,即使已知不能表示为两个充裕数的总和的最大数量小于该限制,也不能通过分析进一步减小该上限.

找到所有正整数的总和,这些正整数不能写为两个数字的总和.

问题的答案是4179871,我的程序显示3797954.

首先,我创建了一个函数来填充数字丰富的[],其中包含28124以下的所有数字.这非常合适,因为我搜索了大量的数字,它们与我的数组完全匹配.

其次,我有另一个数字,所有数字都是1-28123,我假设所有这些都"不能写成两个数字的总和." 这些都写入数组hold [].

最后,我将可以写成的数字作为两个丰富数字的总和,通过在[]中添加所有数字,在[]中加上所有数字,并将hold []的值设置为0.丰富[0到n] +丰富[0到n]] = 0)在hold []中添加所有剩余数字,我只得到3797954

我知道这个程序效率不高,因为它为所有丰富的数字添加了所有丰富的数字,但它应该可以正常工作.它出什么问题了？

#include <iostream>
#include <cmath>

using namespace std;

int hold[28124];
int abundant[7000]; //hold abundant numbers, there are only 6919 abundant numbers below 28123

bool abundance(int x){  //returns true if x is abundant
    int counter = 1;    //holds "proper divisors" of numbers, …

问题是:"写一个函数来找出一个数字是一个素数还是一个完整的数字."

到目前为止,我已经完成了最完美的部分,这就是我所拥有的:

#include <iostream>
using namespace std;
bool perfectNumber(int);
int main()
{
 int number;

 cout<<"Please enter number:\n";
 cin>>number;
 bool perfectNumber(number);

 return 0;
}
bool perfectNumber(int number)
{
 int i;

 int sum=0;
 for(i=1;i<=number/2;i++)
 {
  if(number%i==0)
  {
   sum+=i;
  }
 }
 if (sum==number)
  return i;
 else
  return 0;
}

但是,这段代码似乎有错误.我查看了这本书,但没有谈论这个话题.我想获得有关如何修复此代码的建议.

谢谢!

我正在编写一个可以找到完美数字的程序。阅读完这些完美数后，我发现了它们的列表：完美数列表。目前的输出是：

28         // perfect
496        // perfect
8128       // perfect
130816     // not perfect
2096128    // not perfect
33550336   // perfect

我决定创建数组并将其与数字一起放置，将数字完全分开（没有其余部分）。因此，我将能够通过添加数组的所有元素来验证它是否是一个完美的数字。但应用程序崩溃了，我不明白为什么：

#include <stdio.h>
#include <stdlib.h>

int main()
{
    unsigned long number;
    unsigned long arr2[100] = {0};
    int k = 0;

    for ( number = 0; number <= 130816; number++ )
        if ( 130816 % number == 0 )
            arr2[k++] = number;

    for ( k = 0; k < 100; k++ ) …