Page 3 of 5 First 12345 Last
  1. #41
    tom982's Avatar
    Join Date
    May 2012
    Location
    Southampton, England
    Age
    23
    Posts
    4,328
    • specs System Specs
      • Manufacturer:
        Custom
      • Model Number:
        Custom
      • Motherboard:
        ASUS P8Z77-V PRO
      • CPU:
        Intel Core i7 3770K @4.5GHz
      • Memory:
        Corsair Vengeance 2x4GB 1600MHz LP - White
      • Graphics:
        Gigabyte HD 7850 2GB @1050MHz
      • Sound Card:
        Stock
      • Hard Drives:
        Seagate Barracuda 2TB 7200rpm [Internal], 2x500GB Seagate FreeAgent (External)
      • Disk Drives:
      • Power Supply:
        Corsair TX650W V2 80+ Bronze
      • Case:
        NZXT Phantom 410 White
      • Cooling:
        Corsair H100 CPU Water Cooler, 1x140mm stock fan and 1x120mm stock fan
      • Display:
        LG 23" IPS Monitor (1920*1080)
      • Operating System:
        Windows 10

    Re: 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:


    • Ad Bot

      advertising
      Beep.

        
       

  2. #42
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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 by AceInfinity; 06-08-2013 at 03:32 PM.
    tom982 says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  3. #43
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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 by AceInfinity; 06-20-2013 at 11:50 PM.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  4. #44
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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


  5. #45
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  6. #46
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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


  7. #47
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    Quote Originally Posted by Tekno Venus View Post
    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 by AceInfinity; 06-23-2013 at 08:53 AM.
    Tekno Venus says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  8. #48
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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


  9. #49
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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... :)
    Tekno Venus says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  10. #50
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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

    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


  11. #51
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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 ! Keep it up.
    Tekno Venus says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  12. #52
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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 by Tekno Venus; 06-24-2013 at 03:10 AM.
    AceInfinity says thanks for this.


  13. #53
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    Quote Originally Posted by Tekno Venus View Post
    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.
    Tekno Venus says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  14. #54
    Tekno Venus's Avatar
    Join Date
    Jul 2012
    Location
    UK
    Age
    20
    Posts
    5,803
    • specs System Specs
      • Manufacturer:
        Custom Built
      • Motherboard:
        ASUS Z170I ITX
      • CPU:
        Intel Core i7 6700K
      • Memory:
        16GB DDR4
      • Hard Drives:
        500GB Samsung 850 EVO, 2TB Seagate HDD
      • Power Supply:
        450W Corsair SFX
      • Case:
        Silverstone SG13 ITX
      • Cooling:
        Corsair H60i
      • Display:
        Dell U2715H - 2160x1440 27 inch
      • Operating System:
        Windows 10 Pro x64

    Re: Project Euler

    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:
    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



    Last edited by Tekno Venus; 06-25-2013 at 02:28 PM.


  15. #55
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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.
    Attached Thumbnails Attached Thumbnails Project Euler-list-png  
    Last edited by AceInfinity; 06-25-2013 at 06:47 PM.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  16. #56

    Join Date
    Dec 2012
    Location
    UK
    Posts
    75

    Re: Project Euler

    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?
    Tekno Venus and AceInfinity say thanks for this.

  17. #57
    Laxer's Avatar
    Join Date
    Feb 2012
    Location
    Portland, OR
    Posts
    3,841
    • specs System Specs
      • Motherboard:
        GIGABYTE GA-Z97MX
      • CPU:
        Intel 4690K @ 4.6Ghz
      • Memory:
        Corsair Vengeance Pro 16GB @ 2666Mhz
      • Graphics:
        2x Sapphire 7970s
      • Hard Drives:
        2x Corsair Force 3GT 120GB (RAID 0) + 2x Western Digital Red 3TB (RAID 1)
      • Disk Drives:
        LG Black 10X Blu-ray Burner
      • Power Supply:
        CORSAIR 950HX
      • Case:
        Corsair 350D
      • Cooling:
        Corsair H100i
      • Display:
        3 x 22&quot; Samsung 1080p Displays
      • Operating System:
        Windows 8 Pro x64

    Re: Project Euler

    Welcome in Chikanman

    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

    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

  18. #58

    Join Date
    Dec 2012
    Location
    UK
    Posts
    75

    Re: Project Euler

    Quote Originally Posted by Laxer View Post
    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... I mean, seriously, this forum has more computing qualifications than I've ever seen in one place :)

  19. #59
    AceInfinity's Avatar
    Join Date
    Feb 2012
    Location
    Canada
    Posts
    1,716

    Re: Project Euler

    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 by AceInfinity; 06-26-2013 at 02:45 PM.
    Chikanman says thanks for this.
    \n\n

    Automation Programmer
    Development Site: aceinfinity.net

  20. #60

    Join Date
    Dec 2012
    Location
    UK
    Posts
    75

    Re: Project Euler

    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:



    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

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

Page 3 of 5 First 12345 Last

Similar Threads

  1. [Project] StringCrypt - Work in Progress
    By AceInfinity in forum Programming
    Replies: 1
    Last Post: 10-01-2012, 11:38 PM
  2. Project Ideas
    By HonorGamer in forum Programming
    Replies: 15
    Last Post: 07-29-2012, 05:08 PM
  3. VB Project... To help me learn
    By GZ in forum Programming
    Replies: 7
    Last Post: 06-02-2012, 10:57 PM

Log in

Log in