Springen naar inhoud


- - - - -
Solved

Opdracht 012



  • Log in a.u.b. om te beantwoorden
Er zijn 3 reacties in dit onderwerp

#1 josk79

josk79

    Master Developer

  • Leden
  • PipPipPipPipPip
  • 614 berichten
    Laatst bezocht 30 jan 2017 23:38

Geplaatst op 14 oktober 2010 - 22:43

Citeren

The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?



#2 josk79

josk79

    Master Developer

  • Leden
  • PipPipPipPipPip
  • 614 berichten
    Laatst bezocht 30 jan 2017 23:38

Geplaatst op 14 oktober 2010 - 22:48

De oplossing:

Visual Basic Code:
	Public Class Problem012
		Implements IEulerSolution

		Private Primer As PrimeFinder = New PrimeFinder

		Public Event OnDebugMessage(ByVal str As String) Implements IEulerSolution.OnDebugMessage

		Public Function Solve() As String Implements IEulerSolution.Solve

			Dim trnum As Long = 0, n As Long, i As Integer = 0
			Dim max As Long = 0

			Do
				i += 1
				trnum += i
				Dim factors As List(Of Long()) = primer.GetDividers(trnum)
				Dim dividers As Long = 1
				' If you factor a number into its prime power factors, then the total
				' number of factors is found by adding one to all the exponents and
				' multiplying those results together.
				' Bron: [url]http://mathforum.org...57151.html[/url]
				For Each fac As Long() In factors
					dividers *= fac(1) + 1
				Next
				n = dividers

				If n > max Then
					max = n
				End If
			Loop Until n >= 500

			Return trnum.ToString

		End Function
	End Class


Deze oplossing gebruikt deze priemgetalzoekerklasse die ik heb gemaakt:

Visual Basic Code:
Public Class PrimeFinder
	'v1.00.001
	'Klasse om met priemgetallen te werken
	'De lijst met priemgetallen wordt intern bijgehouden en zal groeien
	'wanneer nodig

	Private primePointer As Integer
	Private primes As List(Of Long) = New List(Of Long)

	Public Sub Reset()
		'Zorg dat NextPrime() weer bij het eerste priemgetal (2) begint
		primePointer = 0
	End Sub

	Public Function Count() As Integer
		Return primes.Count
	End Function

	'Verkrijg het zoveelste priemgetal
	Public ReadOnly Property Prime(ByVal index As Integer) As Long
		Get
			While index > primes.Count - 1
				Prime = NextPrime
			End While

			Prime = primes(index)
		End Get
	End Property

	'Verkrijg volgende priemgetal
	Public Function NextPrime() As Long
		Dim np As Long

		'Lijst leeg, prime is 2
		If primes.Count = 0 Then
			primes.Add(2)
			primePointer = 1
			np = 2
		ElseIf primePointer < primes.Count Then
			'We kennen deze prime al
			np = primes(primePointer)
			primePointer += 1
		Else
			'Volgende prime bepalen
			np = primes.Item(primes.Count - 1) 'Laatste prime
			If np = 2 Then np = 1
			Do
				np += 2
				For Each prime As Long In primes
					'result = Math.DivRem(np, prime, remainder)
					'If remainder = 0 Then GoTo Volgende
					If np Mod prime = 0 Then GoTo Volgende
				Next
				primes.Add(np)
				primePointer = primes.Count
				Exit Do
Volgende:
			Loop
		End If

		Return np
	End Function

	'Verkrijg lijst met alle priemgetallen waar number deelbaar door is.
	'Ieder item in de lijst is een array van 2 Longs
	'De eerste Long is het priemgetal, de tweede Long is de exponent
	'Bijv. {3,2} betekent dat het getal 2x door 3 deelbaar is
	Public Function GetDividers(ByVal number As Long) As List(Of Long())
		Dim factors As List(Of Long()) = New List(Of Long())
		Dim thisprime As Long = 0

		Me.Reset()
		While number > 1
			thisprime = NextPrime()
			If number Mod thisprime = 0 Then
				Dim factor(1) As Long
				While number Mod thisprime = 0
					factor(0) = thisprime
					factor(1) += 1
					number \= thisprime
				End While
				factors.Add(factor)
			End If
		End While
		Return factors
	End Function
End Class



#3 josk79

josk79

    Master Developer

  • Leden
  • PipPipPipPipPip
  • 614 berichten
    Laatst bezocht 30 jan 2017 23:38

Geplaatst op 14 oktober 2010 - 22:52

Misschien een ietwat complexe oplossing, maar ja.... het werkt wel en supersnel.

#4 Supervos

Supervos

    Guru Developer

  • Leden
  • PipPipPipPipPipPip
  • 1396 berichten
    Laatst bezocht 12 jun 2018 07:20

Geplaatst op 16 december 2010 - 22:50

Ik heb volgende code gebruikt en dit werkt ook zeer snel:

Visual Basic Code:
			long result = 0;

			int tri = 3;
			for (int i = 3; result == 0; i++)
			{
				tri += i;
				int dividers = 2;
				double bound = Math.Sqrt(tri);
				if (bound % 1 == 0) dividers++;

				for (int j = 2; j < bound; j++)
				{
					if (tri % j == 0) dividers += 2;
				}
				if (dividers > 500)
					result = tri;
			}


			Console.Write(result);
			Console.ReadKey();

Trouwens, je klasse voor priemgetallen kan nog ietsje beter. Momenteel controleer jij je priemgetallen met alle waarden die je al hebt gevonden maar eigenlijk kan je al veel vroeger stoppen.

als je tot de wortel van je getal gaat ben je al ver genoeg, neem bijvoorbeeld 121
de wortel van 121 is 11, als je 11 vermenigvuldigt met iets groter dan 11 zal je altijd een getal uitkomen groter dan 11, als je deelt zal je bij getallen groter dan 11 als resultaat een getal kleiner dan 11 krijgen

121 / 20 = 6.05





Ook met taq Solved voorzien

0 gebruiker(s) lezen dit onderwerp

0 lid(leden), 0 bezoeker(s), 0 anonieme gebruikers

Inloggen


[Solved] Untitled 1

Met dank aan Jürgen voor de jarenlange inzet van visualbasic.be (anno dec 2000)
Met dank aan Mike en Ronneke voor de jarenlange inzet van vbib.be (anno dec 2010)
Met dank aan PascalBianca voor de jarenlange inzet van vbib.be (anno dec 2016)