項目歐拉數3

Question

首先，這不是作業......在課堂外的這個工作，以獲得一些與Java練習。

public class Problem3 { 
public static void main(String[] args) {  
    int n = 13195; 

    // For every value 2 -> n 
    for (int i=2; i < n; i++) { 
     // If i is a multiple of n 
     if (n % i == 0) { 
      // For every value i -> n 
      for (int j=2; j < i; j++) { 
       if (n % j != 0) { 
        System.out.println(i); 
        break; 
       } 
      } 
     } 
    } 
    } 
} 

我一直在修改代碼，試圖讓它做我想做的事。

隨着問題說，你應該得到5，7，13和29

我得到這些值，加上35，65，91，145，203，377，455，1015，1885年，和2639.我認爲我走在正確的軌道上，因爲我擁有所有正確的數字......只是有一些額外的。

而在檢查一些數字都可以被n整除和作爲素數，這裏的問題是額外的數字不是素數。不知道發生了什麼。

如果有人有任何見解，請分享。

Answer 1

這部分

for (int j=2; j < i; j++) { 
    if (n % j != 0) { 
     System.out.println(i); 
     break; 
    } 

不檢查i是否是素數。除非i很小，否則總是會在某個時間點打印i，因爲存在小於i的數字，它們不會分成n。所以基本上，這將打印出n（例如n == 12不會打印除數4的所有除數，但這是一個例外）。

還要注意算法 - 使用long代替int以避免溢出 - 即使固定檢查除數i是首要決定是否將其打印出來，將需要很長的時間來進行實際的目標運行。您應該進行調查以找到更好的算法（提示：您可能想要查找完整的素數因子分解）。

Answer 2

Brut force還可以用於檢查因素是否爲素數或不是這個問題... 例如。

 for(i=1;i<=n;i++)// n is a factor. 
     { 
     for(j=i;j>=1;j--) 
      { 
      if(i%j==0) 
       { 
        counter++;// set counter=0 befor. 
       } 
      if(counter==2) // for a prime factor the counter will always be exactly two. 
      { 
        System.out.println(i); 
       } 
       counter=0; 
      } 
     } 

Answer 3

我在Java的解決了這個問題，看着我的解決方案有明顯的建議是開始使用的BigInteger，看看在java.math.BigInteger的

文檔

也有很多的這些問題是「加減乘除」問題和「計算機科學」問題一樣多，所以在研究數學問題的時候，要確保你理解數學的合理性，然後再提出算法。蠻力可以工作一段時間，但往往有這些問題的技巧。

Answer 4

不知道Java，但這是我的C代碼，如果它有任何幫助。

# include <stdio.h> 
# include <math.h> 

// A function to print all prime factors of a given number n 
void primeFactors(long long int n) 
{ 
// Print the number of 2s that divide n 
while (n%2 == 0) 
{ 
printf("%d ", 2); 
n = n/2; 
} 
int i; 
// n must be odd at this point. So we can skip one element (Note i = i +2) 
for (i = 3; i <= sqrt(n); i = i+2) 
{ 
// While i divides n, print i and divide n 
while (n%i == 0) 
{ 
printf("%d ", i); 
n = n/i; 
} 
} 

// This condition is to handle the case whien n is a prime number 
// greater than 2 
if (n > 2) 
printf ("%ld ", n); 
} 

/* Driver program to test above function */ 
int main() 
{ 
long long int n = 600851475143; 
primeFactors(n); 
return 0; 
} 

Answer 5

它很好，你正在課堂上處理這些問題。 看到你的代碼。您正在主函數/線程內編寫程序代碼。 改寫功能，先算法思考。 簡單算法來解決這個問題可以是這樣的：

• 1）生成的數字從2開始連續地其爲至少素數，以二分之一萬三千一百九十五。（任何數字總是小於其值的一半）
• 2）檢查生成的數字是否爲素數。
• 3）如果數字是素數，那麼檢查它是否是13195的因子;
• 4）返回最後一個素因子，因爲它將是最大的素因子13195;

還有一個建議是嘗試寫入單獨的函數以避免代碼複雜性。 代碼是這樣的......

public class LargestPrimeFactor { 

public static long getLargestPrimeFactor(long num){ 

    long largestprimefactor = 0; 

    for(long i = 2; i<=num/2;i++){ 

     if(isPrime(i)){ 

      if(num%i==0){ 


       largestprimefactor = i; 

       System.out.println(largestprimefactor); 

      }    
     }    
    } 

    return largestprimefactor; 

} 

public static boolean isPrime(long num){ 

    boolean prime=false; 
    int count=0; 
    for(long i=1;i<=num/2;i++){ 

     if(num%i==0){ 


      count++; 

     } 
     if(count==1){ 

      prime = true; 

     } 
     else{ 

      prime = false; 
     }   
    } 

    return prime; 

} 



public static void main(String[] args) { 

    System.out.println("Largest prime factor of 13195 is "+getLargestPrimeFactor(13195)); 

} 

}