# IntroToAlgorithm3ed / src / projectEuler / 3_v1.go

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53``` ```//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) } ```