//Copyright (C) 2012 Eric Chen(G+ page:HencriceFOSS, gmail:hencrice+FOSS+introtoalgorithm3ed@gmail.com)
//
//This file is a part of introtoalgorithm3ed.
//
//introtoalgorithm3ed is a free software; you can redistribute it and/or modify it under the terms of the GNU General
//Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option)
//any later version.
//
//This software is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the
//implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
//License for more details.
//
//You should have received a copy of the GNU General Public License along with this source file; if not, write to the
//Free Software Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
//Task: Find the number of inversions in the file given.
//The file contains all the 100,000 integers between 1 and 100,000 (including both) in some random order(no integer is repeated).
package main
import (
"fmt"
)
func main() {
//The prime factors of 13195 are 5, 7, 13 and 29. What is the largest prime factor of the number 600851475143 ?
/*I think I can use dynamic programming, start from finding small prime then divide a bigger number, which we don't
know whether it's prime by these smaller primes(we need to store these).
*/
//This version is too slow when target==600851475143
var target, maxPrimeFactor uint64 = 97, 1
smallerPrimes, isPrime := []uint64{2}, true
var i uint64 = 3
for ; i <= target; i++ {
maxPrimeFactor = 1
isPrime = true
fmt.Println("i", i)
for j := len(smallerPrimes) - 1; j > -1; j-- {
//fmt.Println("smallPrime", smallerPrimes[j])
if i%smallerPrimes[j] == 0 {
isPrime = false
maxPrimeFactor = smallerPrimes[j]
break
}
}
if isPrime {
smallerPrimes = append(smallerPrimes, i)
}
}
if target == smallerPrimes[len(smallerPrimes)-1] { //in the condition which target itself is a prime.
maxPrimeFactor = target
}
fmt.Printf("FMax prime factor=%d\n", maxPrimeFactor)
}