Source

IntroToAlgorithm3ed / src / projectEuler / 3_v1.go

Full commit
//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)
}