المشروع يولر السؤال 3 مساعدة

Question

أنا أحاول أن أعمل من خلال المشروع يولر وأنا ضرب حاجز على مشكلة 03.لدي خوارزمية التي يعمل أصغر الأرقام ، ولكن المشكلة 3 يستخدم جدا, عدد كبير جدا.

المشكلة 03: رئيس الوزراء عوامل 13195 5 و 7 و 13 و 29.ما هو أكبر عامل رئيس الوزراء من عدد 600851475143?

هنا الحل في C# و قد تم تشغيله لمدة أعتقد أن ما يقرب من ساعة.أنا لا أبحث عن إجابة لأنني فعلا أريد حل هذا بنفسي.أساسا فقط أبحث عن بعض المساعدة.

    static void Main(string[] args) {
        const long n = 600851475143;
        //const long n = 13195;
        long count, half, largestPrime = 0;
        bool IsAPrime;

        half = n / 2;

        for (long i = half; i > 1 && largestPrime == 0; i--) {
             if (n % i == 0) { // these are factors of n
                count = 1;
                IsAPrime = true;
                while (++count < i && IsAPrime) {
                    if (i % count == 0) { // does a factor of n have a factor? (not prime)
                        IsAPrime = false;
                    }
                }
                if (IsAPrime) {
                    largestPrime = i;
                }
            }
        }

        Console.WriteLine("The largest prime factor is " + largestPrime.ToString() + ".");
        Console.ReadLine();
    }

Answer 1

بالنسبة للمبتدئين, بدلا من البدء في البحث الخاص بك في ن / 2 ، ابدأ في الجذر التربيعي ل n.سوف تحصل على نصف العوامل النصف الآخر الذي لم يكمل.

على سبيل المثال:

n = 27
start at floor(sqrt(27)) = 5
is 5 a factor? no
is 4 a factor? no
is 3 a factor? yes. 27 / 3 = 9. 9 is also a factor.
is 2 a factor? no.
factors are 3 and 9.

Answer 2

long n = 600851475143L; //not even, so 2 wont be a factor
int factor = 3; 
while( n > 1)
{
    if(n % factor == 0)
    {
        n/=factor;
    }else
        factor += 2; //skip even numbrs
}
        print factor;

هذا يجب أن تكون سريعة بما فيه الكفاية...لاحظت هناك حاجة للتحقق من رئيس الوزراء...

Answer 3

في الحقيقة هذا حال كنت لا تحتاج إلى التحقق من بريماليتي فقط إزالة العوامل تجد.تبدأ مع n == 2 و مسح صعودا.عندما الشر-كبيرة-عدد % n == 0, تقسيم الشر-كبيرة-عدد n وتواصل مع أصغر-الشر-عدد.وقف عند n >= الجذر التربيعي(كبيرة-الشر-عدد).

يجب أن لا يستغرق أكثر من بضع ثوان على أي آلة حديثة.

Answer 4

على الرغم من أن السؤال يسأل عن أكبر رئيس الوزراء العامل ، هذا لا يعني بالضرورة أنك يجب أن تجد أن أول واحد...

Answer 5

تحتاج إلى تقليل كمية التحقق تقومون به ...التفكير في ما الأرقام التي تحتاج إلى اختبار.

أفضل نهج تقرأ على غربال Erathosthenes ...يجب أن تحصل وأشار في الاتجاه الصحيح.

Answer 6

أما عن سبب قبول nicf الجواب:

وهو موافق لهذه المشكلة في يولر, ولكن لا تجعل هذا حل فعال في الحالة العامة.لماذا تحاول حتى أرقام العوامل ؟

• إذا كان n هو حتى shift اليسار (القسمة 2) حتى أنه ليس بعد الآن.إذا كان واحد ثم 2 هو أكبر رئيس الوزراء عامل.
• إذا كان n هو حتى لم يكن لديك إلى اختبار حتى الأرقام.
• صحيح أنه يمكنك التوقف في الجذر التربيعي(ن).
• لديك فقط لاختبار يعبي العوامل.قد يكون أسرع إلى اختبار إذا ك يقسم n ثم اختبار بالنسبة بريماليتي على الرغم من.
• يمكنك تحسين الحد الأعلى على الطاير عندما تجد عاملا.

هذا من شأنه أن يؤدي إلى بعض رمز مثل هذا:

n = abs(number);
result = 1;
if (n mod 2 = 0) {
  result = 2;
  while (n mod 2 = 0) n /= 2;
}
for(i=3; i<sqrt(n); i+=2) {
  if (n mod i = 0) {
    result = i;
    while (n mod i = 0)  n /= i;
  }
}
return max(n,result)

هناك بعض مودولو الاختبارات المفرطة ، كما ن لا يمكن أبدا أن يكون مقسوما على 6 إذا كان كل العوامل 2 و 3 قد أزيلت.هل يمكن أن تسمح فقط يعبي أنا.

فقط كمثال على ذلك دعونا ننظر في النتيجة لمدة 21:

21 لا حتى ، وبالتالي ندخل في حلقة مع الحد الأعلى الجذر التربيعي(21) (~4.6).ثم يمكننا تقسيم 21 3 ، وبالتالي النتيجة = 3 n = 21/3 = 7.نحن الآن لا تملك إلا أن اختبار ما يصل إلى الجذر التربيعي(7).الذي هو أصغر ثم 3 ، لذلك نحن القيام به مع حلقة.نعود ماكس ن ونتيجة لذلك ، وهو n = 7.

Answer 7

الطريقة التي فعلت ذلك كان البحث عن يعبي (p) ، ابتداء من الساعة 2 باستخدام غربال إراتوستينس.هذه الخوارزمية يمكن أن تجد كل يعبي تحت 10 مليون دولار <2s على لائق آلة سريعة.

لكل رئيس تجد الاختبار تقسيمه إلى عدد تختبره ضد حتى لا يمكنك أن تفعل قسمة عدد صحيح بعد الآن.(ie.تحقق n % p == 0 و إذا كان هذا صحيحا ، ثم تقسيم.)

مرة واحدة n = 1, أنت القيام به.مشاركة قيمة n التي نجحت في تقسيم هو الإجابة.على sidenote لقد وجدت أيضا كل من رئيس الوزراء عوامل n على الطريق.

PS:كما لوحظ من قبل ، تحتاج فقط إلى البحث عن يعبي بين 2 <= n <= sqrt(p).هذا يجعل غربال إراتوستينس سريعة جدا وسهلة لتنفيذ الخوارزمية لأغراضنا.

Answer 8

عندما تجد الجواب ، قم بإدخال التالي في المتصفح الخاص بك؛)

http://www.wolframalpha.com/input/?i=FactorInteger(600851475143)

Wofram ألفا هو صديقك

Answer 9

باستخدام خوارزمية العودية في جافا يعمل أقل من ثانية ...أعتقد خوارزمية الخاص بك من خلال قليلا كما يتضمن بعض "مجبرا" التي يمكن القضاء عليها.ننظر أيضا في كيفية الحل الخاص بك الفضاء يمكن الحد من الحسابات الوسيطة.

Answer 10

من السهل peasy في C++:

#include <iostream>

using namespace std;


int main()
{
    unsigned long long int largefactor = 600851475143;
    for(int i = 2;;)
    {
        if (largefactor <= i)
            break;
        if (largefactor % i == 0)
        {
            largefactor = largefactor / i;
        }
        else
            i++;
    }

    cout << largefactor << endl;

    cin.get();
    return 0;
}

Answer 11

هذا الحل على C++ أخذت 3.7 ms على Intel Quad Core i5 إيماك (3.1 GHz)

#include <iostream>
#include <cmath>
#include <ctime>

using std::sqrt; using std::cin;
using std::cout; using std::endl;

long lpf(long n)
{
  long start = (sqrt(n) + 2 % 2);
  if(start % 2 == 0) start++;

  for(long i = start; i != 2; i -= 2)
    {
      if(n % i == 0) //then i is a factor of n                                                
        {
          long j = 2L;
          do {
              ++j;
             }
          while(i % j != 0 && j <= i);

          if(j == i) //then i is a prime number                                           
            return i;
        }
    }
}

int main()
{
  long n, ans;
  cout << "Please enter your number: ";
  cin >> n; //600851475143L                                                               

  time_t start, end;
  time(&start);
  int i;
  for(i = 0; i != 3000; ++i)
      ans = lpf(n);
  time(&end);

  cout << "The largest prime factor of your number is: " << ans << endl;
  cout << "Running time: " << 1000*difftime(end, start)/i << " ms." << endl;

  return 0;
}

Answer 12

كل مشروع أويلر المشاكل ينبغي أن تأخذ أقل من دقيقة ، حتى غير محسن العودية التنفيذ في بيثون يستغرق أقل من ثانية [0.09 ثانية (وحدة المعالجة المركزية 4.3 GHz)].

from math import sqrt

def largest_primefactor(number):
    for divisor in range(2, int(sqrt(number) + 1.5)): # divisor <= sqrt(n)
        q, r = divmod(number, divisor)
        if r == 0:
            #assert(isprime(divisor))
            # recursion depth == number of prime factors,
            # e.g. 4 has two prime factors: {2,2}
            return largest_primefactor(q) 

    return number # number is a prime itself

Answer 13

قد ترغب في رؤية هذا:هل هناك خوارزمية بسيطة التي يمكن أن تحدد إذا كان X هو رئيس الوزراء و لا تخلط بين البشر مجرد مبرمج ؟

وأنا أحب lill الطين الحل:

تتطلب "mathn.rb"
يضع 600851475143.prime_division.الماضي.أولا

راجعت هنا

Answer 14

ربما يعتبر من الغش ، ولكن احتمال واحد في هاسكل هي كتابة (سجل أنا كتبت خطوط نفسي ولم فحص eulerproject المواضيع);

import Data.Numbers.Primes
last (primeFactors 600851475143)

Answer 15

حاول استخدام ميلر-رابين بريماليتي الاختبار لاختبار عدد من الوزراء.التي ينبغي تسريع الأمور إلى حد كبير.

Answer 16

وثمة نهج آخر هو الحصول على جميع الأعداد الأولية حتى ن/2 أولا ثم تحقق إذا كان معامل 0.خوارزمية كنت الحصول على جميع الأعداد الأولية حتى n يمكن العثور على هنا.