Project Euler

I'm no programmer, yet, but I did manage to find some code to solve #60. It didn't take long at all to find and I'm sure you could easily do the same if you were really stuck, but I just wanted to let you know that it just got the answer in just under 7.5 seconds so if yours is taking a while to iterate then it might be worth thinking about a different approach :)

I'll post, but hide, the code so it doesn't ruin it for you.

Read More:
 
I did look, but I was hoping to find something other than just plain iterative strategies. It seems THE way to go is a boolean table, as it makes that 7.5 seconds look like way too much time. That C# code above is also not very well formed, It's using an ArrayList I see, which already tells me that the 7.5 seconds can be reduced if a List<T> was used instead. I like solving these on my own though, solutions are posted everywhere up until about problem ~#150. Anything past that is hard to come by, and past 300 there's usually nothing.

With the following code it takes about a couple seconds or less:
Code:
#include <iostream>
#include <vector>
#include <ctime>

using namespace std;

#define N 100000000
#define M 1229

vector<int> primes;
bool prime[N];
bool PP[M][M];

void Eratosthenes()
{
     memset(prime , true , N);
     for(long long i = 2 ; i<N ; i++)
             if (prime[i]){
                          primes.push_back(i);
                          for(long long t = i*i ; t<N ; t+=i)
                                  prime[t] = false;
             }
};

int conc(int a , int b)
{
    int tmp = b;
    do
    {
        a*=10;
        tmp/=10;
    }while(tmp>0);
    return a+b;
    
};

void prm(int a, int b )
{
         PP[b][a] = prime[ conc( primes[a],primes[b]) ] && prime[ conc(primes[b],primes[a] ) ];
         PP[a][b] = PP[b][a];
};

int main()
{    
    clock_t start(clock());
    
    Eratosthenes();
    
    clock_t mid(clock()); cout<<"\nTime1: "<<mid-start<<"\n\n";
    
    for(int i = 0 ; i<M ; i++)
          for( int j = i ; j <M ; j++)
              prm( i , j  ) ;


    for(int a = 0 ; a<M ; a++) 
    for(int b = 0 ; b<a ; b++) if ( PP[a][b])
    for(int c = 0 ; c<b ; c++) if ( PP[b][c] && PP[a][c] )
    for(int d = 0 ; d<c ; d++) if ( PP[a][d] && PP[b][d] && PP[c][d] )
    for(int e = 0 ; e<d ; e++) if ( PP[a][e] && PP[b][e] && PP[c][e] && PP[d][e] )
    {
            int tmp = primes[a]+primes[b]+primes[c]+primes[d]+primes[e];
            cout<<primes[a]<<" "<<primes[b]<<" "<<primes[c]<<" "<<primes[d]<<" "<<primes[e]<<"   ";
            cout<<tmp<<" \n";
    }

    clock_t finish(clock()); cout<<"\nTime2: "<<finish-mid<<"\nTime: "<<finish-start;
    return 0;
};
 
Last edited:
Here was my solution in C++ for #46:
Code:
#include "stdafx.h"
#include <iostream>
#include <vector>

typedef std::vector<int>::iterator v_iter;

bool isPrime(int n)
{
    if (n < 0) n = -n;
    for (int i = 2; i * i <= n; i++) if (n / i - (n - 1) / i == 1) return false;
    return true;
}

void getPrimes(std::vector<int>& sieve, int limit)
{
    sieve.clear();
    sieve.push_back(2);
    int x = 3;
    do
    {
        if (isPrime(x)) sieve.push_back(x);
        x += 2;
    } while (x < limit);
}

int getNextOddComposite(int& i)
{
    do { i += 2; } while (isPrime(i));
    return i;
}

int main()
{
    int x = 5;
    std::vector<int> primes;
    bool cond = true;
    while (cond)
    {
        cond = false;
        getNextOddComposite(x);
        getPrimes(primes, x);
        for (v_iter it = primes.begin(); it != primes.end(); it++)
        {
            for (int b = 1; (2 * b * b) + *it <= x; b++)
            {
                if ((2 * b * b) + *it == x)
                {
                    cond = true;
                    break;
                }
            }
            if (cond) break;
        }
    }
    std::cout << "Ans: " << x << std::endl;
    getchar();
    return 0;
}

This isPrime() function has a complexity of O(sqrt(n)).
 
Last edited:
I've only recently started VB.NET (a few months ago) and decided to give project euler a go (or at least some of the easy questions)

Here are my incredibly inefficient answers in VB.NET to question 1 and 2. . .

Question 1

Code:
Module Module1

    Sub Main()
        Dim i As Long = 0
        Dim sum As Long = 0

        Do Until i = 1000
            If i Mod 3 = 0 Then
                sum += i
            ElseIf i Mod 5 = 0 Then
                sum += i
            End If
            Console.WriteLine(i)
            i += 1
        Loop
        Console.ReadLine()
        Console.WriteLine("Answer is. . ." & sum)

        Console.ReadLine()
    End Sub

End Module

Question 2

Code:
Module Module1
    Sub Main()
        Dim x As Integer = 1
        Dim y As Integer = 1
        Dim z, z2 As Decimal
        Dim sum As Long = 0
        Console.WriteLine(x)
        Console.WriteLine(y)
        z = x + y
        Console.WriteLine(z)
        sum += z
        z2 = z + y
        Try
            Do While z2 < 4000000
                Console.WriteLine(z2)
                z = z + z2
                If z Mod 2 = 0 Then
                    sum = sum + z
                End If
                Console.WriteLine(z)
                z2 = z2 + z
                If z2 Mod 2 = 0 Then
                    sum = sum + z2
                End If
            Loop
        Catch ex As Exception
            Console.WriteLine(ex.Message)
        End Try
        Console.ReadLine()
        Console.WriteLine("Sum of even values is. . .")
        Console.Write(sum)
        Console.ReadLine()
    End Sub
End Module
 
for your first one, why not use a for loop to do the incrementing? Also, you can use OrElse since sum += 1 is the same in both branches.

You should only need Integer too:
Code:
Sub Main()
	Dim sum As Integer = 0
	For i As Integer = 1 To 1000
		If i Mod 3 = 0 OrElse i Mod 5 = 0 Then
			sum += i
		End If
	Next
	Console.WriteLine("Answer is. . ." & sum)
	Console.ReadLine()
End Sub

Why do you have a Try Catch in the second one though? I can't see anything at first glance that would throw an exception and you're not dividing by 0 anywhere.
 
Hey Ace,

Firstly, thanks for giving me some advice and information. As I said, I have only been learning VB for the past 2 and a bit months so am really inexperienced. Hence I need all the tips I can get :-)

I was going to use a for loop but for some reason didn't. I can't quite remember my logic behind it though ;-) Would a for loop have any benefits in this scenario?

Regarding OrElse, I would have used that had I known of its existence ;-) I've never seen or used that before. I thought I did use integer, or at least I meant to, but for some reason used long.

Regarding the Try Catch, I was using the program to list as many Fibonacci numbers as possible and didn't want it to crash when it exceeded the maximum length number for that variable. I just didn't remove it for my final code. Should I have? Is there a downside to using it?

Once again, any advice is appreciated

Stephen
 
Hey Ace,

Firstly, thanks for giving me some advice and information. As I said, I have only been learning VB for the past 2 and a bit months so am really inexperienced. Hence I need all the tips I can get :-)

I was going to use a for loop but for some reason didn't. I can't quite remember my logic behind it though ;-) Would a for loop have any benefits in this scenario?

Regarding OrElse, I would have used that had I known of its existence ;-) I've never seen or used that before. I thought I did use integer, or at least I meant to, but for some reason used long.

Regarding the Try Catch, I was using the program to list as many Fibonacci numbers as possible and didn't want it to crash when it exceeded the maximum length number for that variable. I just didn't remove it for my final code. Should I have? Is there a downside to using it?

Once again, any advice is appreciated

Stephen

I know, so don't get too frustrated :) You will learn with time. Any advantages of the for loop over the loop you have? Scope. But a for loop is much more easy to maintain for temp increment variables in specific. OrElse is the equivalent of AndAlso instead of And. OrElse and AndAlso are opposites of each other, but both are short circuiting operators.

Downsides to using Try.. Catch? Having an exception thrown is costly for performance, some people misuse it as a way of exception handling though. For instance a try catch around a divide by 0 operation, is less efficient than checking the divisor for equality against 0, and dealing with it through other logic (if... then maybe?). See this: Exception Handling

Your code is not bad though, and definitely not the worst I have seen either. You'll go far though I'm sure. I know what your determination is like.

I have helped many people learn VB.net, and the common things I usually see are:

- Try.. Catch overuse & mis-use
- Wrong datatypes being used
- No Exception handling
- Too many variables being declared (and especially member variables (or "global" variables) without reason)

And most the most infamous bad habit I see, is allowing implicit conversions to take place. For example, they don't understand that double quotes mean a string value, and try to assign that as a numeric value type such as an Integer:
Code:
Dim i As Integer = "10"

And because an implicit conversion happens here, I usually also see people trying to do addition with strings, and wondering why it concatenates when using the + operator. Otherwise, in the case that a string + an int is being implicitly decided as int + int for you, that is still not good. Cast the string to an int, then do the math with these variables. Implicit conversions are bad for performance.

To help you with this, make sure you have this at the top of your code at all times, because it is off by default:
Code:
Option Strict On

This goes above everything in your source code, it should be line #1.

edit: Try problem #3 :) It could be fun for you. I'll give you some starter tips:

- A prime is not even, with the exception of 2, 1 and 0 are special numbers, so this will help with your IsPrime() function, but also when you loop through values to find prime divisors of the number (600851475143). The largest prime factor can't be 2, because this number is not an even number. So you would start with 3, and increment by 2, checking each number to make sure you only check odds. This speeds up the process.
- You don't need to check from N, all the way up to the number itself to find prime divisors, let alone divisors of this number. Divisors of 2, and half the number should be as high as anybody would go, without further math knowledge. The other divisors are 1 and the number itself. If this number itself is prime, then obviously it would be the highest prime divisor, but it's not prime :)
 
Last edited:
Ace,

Wow, thanks for all that information. Much appreciated. :)

I've begun work on #3, but my program is VERY slow. It will take hours to work out the answer atm, I've not let it finish but it got to 0.005% complete after 10 mins (I added a percentage counter).

Am I missing something obvious that's making it that slow or am I just doing to many checks? I took your hints on board as best I could when making the code.

Here is the current code. It works (I've tested smaller numbers), but is far too slow to be able to check the big number I need to check...

Code:
Option Strict On
Module Module1
    Sub Main()
        Dim input As Decimal
        Console.WriteLine("Enter a number")
        input = CDec(Console.ReadLine())

        Dim half As Decimal = input / 2
        Dim factor As Decimal
        Dim highestFact As Decimal = 1
        Dim percent As Decimal

        For factor = 3 To half Step 2
            If input Mod factor = 0 Then
                highestFact = factor
                input = input / highestFact
            End If
            percent = factor / half * 100

            Console.Write("{0}Percent Complete: {1}%", ControlChars.Cr, percent)
        Next

        Console.WriteLine(ControlChars.NewLine)

        If highestFact = 1 Then
            Console.WriteLine("The original number is prime!")
        Else
            Console.WriteLine("Final Factor.... " & highestFact)
        End If
        Console.ReadLine()
    End Sub

End Module

Any hints? Don't give me the whole answer, just a little guidance would be appreciated!

Thanks!

Stephen
 
Okay, so as I mentioned, unless the number itself is a prime, in which case 1 and itself would be the factors here, 1 is not a prime anyways, and this means the next divisor would be 2, and it's opposite, which is half of that number. You are checking for the highest prime factor, so why not start from the number divided by 2, and count downwards? :)

The number itself in this case is not prime, so starting from # / 2, and counting downwards until you find the first factor that is also prime would be the best solution here.

600851475143 /2 = 300425737571.5, which if you're using an integer would round you up to 300425737572, which is an even number. An even number is never prime, with the exception of 2, but 2 is a low number and definitely not going to be the highest prime factor in this case. Therefore, take this value (300425737572) and subtract 1 from it to make it odd. ** Assuming we don't know whether half the number is even or odd, you can check that using the Mod operator in VB.net.

-> If a NUMBER Mod 2 = 0, then 2 is evenly divisible with no remainder (0), and thus this number is even. Else, the number is odd. If it's even, you either want to add or subtract 1 to make it odd.

Why? Primes are never even remember with the exception of 2. So once we have an odd number to start with, we can start counting down and skipping every even number along the way. If you had a prime checking function, this would avoid that expensive computation for checking primality of an even number greater than 2, which is useless.

I would suggest putting this prime check into a function that returns a boolean though for true if prime, false if non-prime however. It would make your code much easier to read, and easier for you to maintain. Functions are saviors...

If you'd like to see how an efficient Prime checking function looks like, here's a function I wrote in C++ and have been using for Project Euler:
Code:
bool isPrime(int n)
{
	if (n < 0) n = -n;
	for (int i = 2; i * i <= n; i++) if (n / i - (n - 1) / i) return false;
	return true;
}

The complexity of this function is O(sqrt(n)), but you don't need to know that kind of stuff at this point when you're only learning.

In essence, you don't actually need to check up to the number / 2 to see if it's prime or not. You only need to check up to the square root of the number. :) I hope that is some good insight. These challenges, although some may be intimidating at first, are VERY good for learning programming in my opinion. They require you to think about fast and efficient ways of dealing with problems. If you spend enough time on them, they get you thinking in good ways that help you with your programming. At first, most people try non-optimized code for these problems to see if they can get it, and sometimes it doesn't work because it makes things too slow.

That's expected at first. These problems will help you though... :)
 
Sorry Ace, you've completely confused me here........ I'm glad of the extra information, but just a little overwhelmed and confused....

I may ramble a bit here, sorry! I'm just trying to get everything straight in my head, I've taken on a lot today! :-)

---------------------------

The whole idea is to check for the highest prime factor of the number correct? I'm going to explain how I want my code to work in English a second:

- User inputs a number
- Perform isPrime function on original number. If the original number is prime, return true and output "Is Prime" and do no further processing
- If isPrime returns false, perform prime factor check
- Print the highest prime factor found by the prime factor checker

Does this make sense?

What I can't work out how to do is both the isPrime function and the Prime Factor check. Wait, that's effectively all of it :lol:

So, my original prime factor check worked as follows:

- Loop, starting from 3, until half of the original number
- If the original number divided by that factor is 0, then the currently found highest factor is that factor that the loop has just done. Divide the original number by that factor and store to variable
- Divide that new variable by the next factor and continue.

Typing that makes me realise that that code was flawed. I'm not quite sure exactly how, but in English it seems flawed....

------------------

I've come back to this post 1/2 an hour later now... Let's see where I am now:

I have made a simple prime checking function. This will be run when the number is imputed, to save processing if the number is already prime. I think I went about this inefficiently again, but your post confused me.

Code:
    Private Function isPrime(ByVal num As Long) As Boolean

        Dim limit As Long = CLng(num / 2)

        If num Mod 2 = 0 Then
            Return False
        End If

        For i As Long = 3 To limit Step 2
            If num Mod i = 0 Then
                Return False
            End If
        Next

        Return True
    End Function

I found working from smallest to largest was fastest because you're more likely to get a hit was smaller numbers earlier than if you worked from the number down to 3. So, now I have a program to check if something is prime... It actually works really quickly, even on the large number. It may not be the most efficient function, but it works quickly...

Code:
Option Strict On
Module Module1

    Private Function isPrime(ByVal num As Long) As Boolean

        Dim limit As Long = CLng(num / 2)

        If num Mod 2 = 0 Then
            Return False
        End If

        For i As Long = 3 To limit Step 2
            If num Mod i = 0 Then
                Return False
            End If
        Next

        Return True
    End Function

    Sub Main()
        Dim input As Long


        Console.WriteLine("Enter a number")
        input = CLng(Console.ReadLine)


        Console.WriteLine("Is it prime? " & isPrime(input))
        Console.ReadLine()
    End Sub

End Module

Now I need to work on the prime factor checking part of it. Here is my plan, again, not sure if it's the best or not...

- Find square root of number
- Perform check as in original code, I think...

Oh, let's go with it, I'll compose the rest in a bit....

---------

Right, I'm stopping for tonight before I go insane.....

This is my code at this current point in time:

Code:
Option Strict On
Module Module1

    Private Function isPrime(ByVal num As Long) As Boolean

        Dim limit As Long = CLng(num / 2)

        If num Mod 2 = 0 Then
            Return False
        End If

        For i As Long = 3 To limit Step 2
            If num Mod i = 0 Then
                Return False
            End If
        Next

        Return True
    End Function

    Private Function factorFinder(ByVal num As Long) As Decimal
        Dim toCheck As Decimal = CDec(System.Math.Sqrt(num))

        Dim factor As Long
        Dim highestFact As Decimal = 1

        toCheck = Math.Round(toCheck) + 1


        For factor = 3 To CLng(toCheck) Step 2
            If toCheck Mod factor = 0 Then
                highestFact = factor
                toCheck = toCheck / highestFact
            End If
        Next

        Return highestFact
    End Function

    Sub Main()
        Dim input As Long
        Dim resultIsPrime As Boolean


        Console.WriteLine("Enter a number")
        input = CLng(Console.ReadLine)

        resultIsPrime = isPrime(input)

        Console.WriteLine(ControlChars.NewLine)

        If resultIsPrime = True Then
            Console.WriteLine("Original number was prime.")
        Else
            Console.WriteLine("Not prime")
            Console.WriteLine(factorFinder(input))
        End If

        Console.ReadLine()

    End Sub

End Module

It works with 13195, giving the answer as 29. But it gives the answer for 600851475143 as 775147, which isn't even divisible by 600851475143. 600851475143 / 775147 = 775145.19845010043256311383518223 ???????

---------------

YES!!! DONE IT!!! :-D :-D :-D :-D

It's far, far faster, completing in less than 1 second. It's only taken 2 hours to do!

My final code:

Code:
Option Strict On
Module Module1

    Private Function isPrime(ByVal num As Long) As Boolean

        Dim limit As Long = CLng(num / 2)

        If num Mod 2 = 0 Then
            Return False
        End If

        For i As Long = 3 To limit Step 2
            If num Mod i = 0 Then
                Return False
            End If
        Next

        Return True
    End Function

    Private Function factorFinder(ByVal num As Long) As Decimal
        Dim max As Decimal = CDec(System.Math.Sqrt(num))

        Dim factor As Long
        Dim highestFact As Decimal = 1

        max = Math.Round(max) + 1


        For factor = 3 To CLng(max) Step 2
            If num Mod factor = 0 Then
                highestFact = factor
                num = CLng(num / highestFact)
            End If
        Next

        Return highestFact
    End Function

    Sub Main()
        Dim input As Long
        Dim resultIsPrime As Boolean


        Console.WriteLine("Enter a number")
        input = CLng(Console.ReadLine)

        resultIsPrime = isPrime(input)

        Console.WriteLine(ControlChars.NewLine)

        If resultIsPrime = True Then
            Console.WriteLine("Original number was prime.")
        Else
            Console.WriteLine("Not prime")
            Console.WriteLine(factorFinder(input))
        End If

        Console.ReadLine()

    End Sub

End Module
Sorry for my babble and rambling!! If you've made it to this point, I am amazed!

OK Ace, I'm now less confused! :) What else can I do to my code to make it better??

Stephen
 
Alright, now that you are done, I'll show you optimizations. I'll just go through a list of things to help...

- Try not to compare booleans with True for validation, they get evaluated as expressions which evaluate to a single boolean anyways, thus True = True, gets simplified to just True, and True = False gets simplified to False.

You only need:
Code:
If Boolean Then...

Not:
Code:
If Boolean = True Then...

- For scope reasons, I avoid variable creation unless the value is going to be used more than once, In this case resultIsPrime is only used really once, so you don't need the variable to store the boolean:

Code:
If IsPrime(num) Then

Scope is an easy concept, and applies to pretty much all programming languages in some way. You'll find lots of informaiton about it.

- Your prime function would say that 2 is not prime as an input when calling that function. You need something like this in there before you evaluate Mod 2 on the input and return False:
Code:
If input = 2 Then
	Return True
End If

- As a note, you don't need to round Decimals (in your Factor finder function) if you just stick with the Integer datatype. Decimals are automatically rounded up because an Integer doesn't have a decimal value.

Assign 4.1 to an Integer and it will store a value of 5 for you. The value is rounded up regardless, so that is something to keep note of.

- For optimization, your Factor Finder function should cound DOWN.

- A factor will never have a decimal and Primes neither, so you should be returning an Integral type for the FactorFinder function too.

Here's some code I put together just now:
Code:
Sub Main()
	Const num As Long = 600851475143
	Dim answer As Long
	If IsPrime(num) Then answer = num _
	Else answer = GetHighestPrimeFactor(num)
	Console.WriteLine("Ans: {0}", answer)
	Console.ReadKey()
End Sub

Public Function IsPrime(input As Long) As Boolean
	If input = 2 Then Return True
	If input = 1 OrElse input Mod 2 = 0 Then Return False
	Dim limit As Long = CLng(Math.Sqrt(input + 1))
	For n As Long = 3 To limit Step 2
		If input Mod n = 0 AndAlso n <> input Then Return False
	Next
	Return True
End Function

Private Function GetHighestPrimeFactor(num As Long) As Integer
	Dim max As Integer = CInt(Math.Sqrt(num))
	If max Mod 2 = 0 Then max += 1
	For n As Integer = max To 3 Step -2
		If num Mod n = 0 AndAlso IsPrime(n) Then Return n
	Next
	Return 0
End Function

If you have any questions, just ask.

Well done on completing the problem though ! :thumbsup2: Keep it up.
 
Thanks again for all your help and support. I think I've learnt more in the past few days speaking to you than I have over the past two months! :-D

After reading your above post, all my questions are answered. It all makes sense now! There is only one thing left intriguing me. You write a lot of your code on single lines, such as some if statements whereas I often spread my code out a lot. Is there an advantage of using less lines bar a smaller file size? Or is it just personal preference?

But once again, thanks for all your help, it's really appreciated!

Stephen
 
Last edited:
Thanks again for all your help and support. I think I've learnt more in the past few days speaking to you than I have over the past two months! :-D

After reading your above post, all my questions are answered. It all makes sense now! There is only one thing left intriguing me. You write a lot of your code on single lines, such as some if statements whereas I often spread my code out a lot. Is there an advantage of using less lines bar a smaller file size? Or is it just personal preference?

But once again, thanks for all your help, it's really appreciated!

Stephen

It's personal preference, whatever you find more readable, is what you should use. For me, I usually compact it as much as it still is kept readable to me, when I have a standard function that I know I'm no longer going to change. My IsPrime function was tested vigorously and is well optimized, so I'm happy with that, I just didn't want it occupying the majority of my code, so that's why I do things like that.

Same thing as in C++, where I may do something like this:
Code:
if (???) ...

Instead of:
Code:
if (???)
{
...
}

I like preserving linespace, as long as horizontally my code doesn't stretch to far either... It minimizes the scrolling and I find that easier when reviewing code. I'll do it even more in VB.net because since it uses words, there is no bracket matching, so it's easier to see what is what (disregarding indentation), when you can see things on one line if the code is short enough. In C#/C/C++ I have bracket matching and highlighting.
 
Hmm... My current code for #4. It works, but is very inflexible because it only works with 6 digit palindromes because it's done with a fixed If statement. It does work however, and I'll post it. I'm going to work out a way to make it more flexible because I feel my way is no where near the best way...

Anyhow:

#4
Code:
Option Strict On
Module Module1

    Private Function isPalindrome(ByVal num As Integer) As Boolean
        Dim stringNum As String = num.ToString
        Dim length As Integer = stringNum.Length
        If stringNum.Substring(0, 1) = stringNum.Substring(length - 1, 1) AndAlso stringNum.Substring(1, 1) = stringNum.Substring(length - 2, 1) _
        AndAlso stringNum.Substring(2, 1) = stringNum.Substring(length - 3, 1) Then Return True
        Return False
    End Function

    Private Function checker() As Integer
        For i As Integer = 999 To 900 Step -1
            For j As Integer = 999 To 900 Step -1
                If isPalindrome(i * j) Then Return i * j
            Next
        Next
        Return 0
    End Function

    Sub Main()
        Console.WriteLine(checker)
        Console.ReadLine()
    End Sub

End Module

and my revised code for #3...

Code:
Option Strict On
Module Module1

    Private Function isPrime(ByVal num As Long) As Boolean
        Dim limit As Long = CLng(num / 2)
        If num = 2 Then Return True
        If num Mod 2 = 0 Then Return False
        For i As Long = 3 To limit Step 2
            If num Mod i = 0 Then Return False
        Next
        Return True
    End Function

    Private Function factorFinder(ByVal num As Long) As Long
        Dim max As Integer = CInt(System.Math.Sqrt(num))
        If max Mod 2 = 0 Then max += 1
        For i As Integer = max To 3 Step -2
            If num Mod i = 0 AndAlso isPrime(i) Then
                Return i
            End If
        Next
    End Function

    Sub Main()
        Dim input As Long
        Console.WriteLine("Enter a number")
        input = CLng(Console.ReadLine)
        Console.WriteLine(ControlChars.NewLine)
        If isPrime(input) Then
            Console.WriteLine("Original number was prime.")
        Else
            Console.WriteLine("Highest Prime Factor is {0}", factorFinder(input))
        End If
        Console.ReadLine()

    End Sub

End Module

Edit - A slighly unusual but more flexible method for #4. I like this, it works better than the original becasue if needs be, it can be used to check almost any length of palindromic number

Code:
[/B]Option Strict On
Module Module1

    Private Function isPalindrome(ByVal num As Long) As Boolean
        Dim result As Integer = 0
        Dim stringNum As String = num.ToString
        Dim length As Integer = stringNum.Length
        For i As Integer = 0 To CInt(length / 2)
            If stringNum.Substring(i, 1) = stringNum.Substring(length - (i + 1), 1) Then result += 1
        Next
        If result <= length / 2 Then Return False Else Return True
    End Function

    Private Function checker() As Integer
        For i As Integer = 999 To 900 Step -1
            For j As Integer = 999 To 900 Step -1
                If isPalindrome(i * j) Then Return i * j
            Next
        Next
        Return 0
    End Function

    Sub Main()
        Console.WriteLine(checker)
        Console.ReadLine()
    End Sub

End Module

[B]


 
Last edited:
If you want to take a look, here's some recursive examples of an IsPalindrome function I wrote for string objects:
Code:
Private Sub MyMethod()
	Const s As String = "GoHangASalamiImALasagnaHog" ' GoHangASalamiImALasagnaHog
	Console.WriteLine("IsPalindrome (Case sensitive): {0}", IsPalindrome(s, 0, s.Length - 1))
	Console.WriteLine("IsPalindrome (Ignore case): {0}", IsPalindrome(s, 0, s.Length - 1, StringComparison.OrdinalIgnoreCase))
End Sub

Public Function IsPalindrome(s As String, lowerIndex As Integer, upperIndex As Integer) As Boolean
	Return IsPalindrome(s, lowerIndex, upperIndex, StringComparison.InvariantCulture)
End Function

Public Function IsPalindrome(s As String, lowerIndex As Integer, upperIndex As Integer, compareMode As StringComparison) As Boolean
	If upperIndex <= lowerIndex Then Return True
	If Not s(lowerIndex).ToString().Equals(s(upperIndex), compareMode) Then Return False
	Return IsPalindrome(s, lowerIndex + 1, upperIndex - 1, compareMode)
End Function

I actually wrote a full collection of helper functions over the time I've been doing Project Euler questions. It's in C#, but if you want I can pass them over to you... You can use an online converter if needed, the most reliable one I've found is Telerik's Online Converter (easily found by Google/Bing). The very odd time it can't convert, but if that's the case, then you can ask me about a function or method that you couldn't understand and could not convert. I know both languages.

Here's a screenshot of my solution with a few of these classes: *see attachment*

Note: This is THE project I use whenever I'm answering online questions to test code and help people with C#. I have another one dedicated to the same purpose for VB.net as well. Nearly everything with testing goes into here though. Now, there's some very advanced code in here, as well as basic code, but nonetheless it's always good to see as much code as possible when learning to see how others do things. There's certain habits you place into your code routinely once you have a bit more time invested into a certain programming language, and this applies with VB.net too, as well as pretty much every other programming language out there.
 

Attachments

  • list.png
    list.png
    16.5 KB · Views: 6
Last edited:
Well, I'll start by saying I'm never letting Stephen challenge me to do anything ever again!
I've also been learning VB.NET, but for a laugh last week I started learning C++, and then he says to me,
"Hey, have you ever heard of Project Euler?"

So long story short, I did the first two (and most of the third) in C++... Then for some reason yesterday half my projects got deleted.
Starting from scratch with Euler 3, I've got:
Code:
#include "stdafx.h"
#include <iostream>
#include <math.h>
#include <cmath>
using namespace std;


bool findIfPrime(long num)
{
    if(num==2){return true;}
    if(num==1|num%2==0){return false;}
    int limit = ceil(sqrt(num));
    for(int i=3;i<=limit;i+=2){
        if(num%i==0){return false;}
    }
    return true;
}
Which I think should work to find primes.

Looking at your factor-finding functions, though, there's something I can't figure out. You start from the square root of the number, and count down to three. What if there's factors larger than the square-root, prime or otherwise? A quick example - 34 equals 2*17. Both are prime, but 17 is larger than the square root and therefore surely wouldn't be detected? If anything, it looks like you should be returning num/n, since each factor below the square root will have a counterpart above it.

Anyway, help and advice gratefully accepted. A certain someone told me you're even better with C languages than VB, so I'm expecting to be made to look like a fool. On the other hand, I've only doing C++ (the only C language I've ever tried) for a week about 5 and a half days so go a little easy?
 
Welcome in Chikanman :wave:

To give you a slight idea of the skill set here, I just finished my 5th term of dedicated C/C++ programming(I'm a junior/3rd year at a uni) and I am one of the more novice programmers here :lolg:

It is worth noting that everyone here is respectful so there is no need to think you will look like a fool.

Just ask John(JCgriff) about his mice :lol:
 
It is worth noting that everyone here is respectful so there is no need to think you will look like a fool.
I know, I wasn't commenting that you were all horrible people, I was simply making the point that you're all WAY better at this than me... :lol: I mean, seriously, this forum has more computing qualifications than I've ever seen in one place :)
 
Glad to see that you're trying to challenge yourself Chikanman, good job :) You're right though I didn't notice that, I mentioned starting from half the number if the number itself was not prime, but you only need to check up to the sqrt of the # for checking primality. One thing I noticed in your code:
Code:
#include <math.h>
#include <cmath>

You only need to #include one or the other, typically <cmath> in C++ and <math.h> in C I believe, but it really doesn't matter. Try this as your prime checking function:
Code:
bool isPrime(long n)
{
    if(n==2) return true;
    if(n<2|n%2==0) return false;
    int limit = (int)sqrt(n);
    for(int i=3;i<=limit;i+=2) if(n%i==0) return false;
    return true;
}

I modified a few things, but this is how my prime function looks that I regularly use
 
Last edited:
Ok, I've messed something up. My function works... but only for numbers under 1000..? 999 comes out fine, but 1000 just gives me a blank console, as does any larger number. My debug and console look something like this:

pa0e.png


And my code is:
Code:
#include "stdafx.h"#include <iostream>
#include <cmath>
using namespace std;


bool findIfPrime(long num)
{
    if(num==2){return true;}
    if((num==1)|(num%2==0)){return false;}
    int limit = ceil(sqrt(num));
    for(int i=3;i<=limit;i+=2){
        if(num%i==0){return false;}
    }
    return true;
}


int findHighestPrimeFactor(long num)
{
    if(findIfPrime(num)){return num;}
    int max = sqrt(num);
    for(int i = 2; i <= max; i++){
        if(num%i==0 & findIfPrime(num/i)){return num/i;}        
    }
    for(int i = max; i >= 2; i++){
        if(num%i==0 & findIfPrime(i)){return i;}
    }
    return 0;
}




int main()
{
    long test = 1000;
    cout << findHighestPrimeFactor(test);
    cin.get();
    cin.get();
    return 1;
}

Little help? I don't want to be told the answer, but a little pointer might be nice :smile9:

ADDITIONAL: Just found this. When I run it, I get "The program '[10884] Projecteuler3fix.exe' has exited with code -1073741510 (0xc000013a)."
 

Has Sysnative Forums helped you? Please consider donating to help us support the site!


Write your reply...
Back
Top