From Friday, April 19th (11:00 PM CDT) through Saturday, April 20th (2:00 PM CDT), 2024, ni.com will undergo system upgrades that may result in temporary service interruption.

We appreciate your patience as we improve our online experience.

Example Code

Project Euler Problem 10

Code and Documents

Attachment

Download All

Overview

This VI shows how to solve Project Euler Problem #10

 

Description

Project Euler Problem #10:

The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.

Find the sum of all the primes below two million.

 

 

Requirements

Software

LabVIEW 2013 (or compatible), LabVIEW Mathscript RT Module

 

Steps to Implement or Execute Code

  1. Set "Primes Below..." Value to 2 Million
  2. Run VI

 

Additional Images or Video

1-381 BD.png

 

**This document has been updated to meet the current required format for the NI Code Exchange.**

 

 

Rob W.

Example code from the Example Code Exchange in the NI Community is licensed with the MIT license.

Comments
thoult
Active Participant
Active Participant
on

A little train of thought from a self confessed ProjectEuler addict. Bear with me, as there are a lot of buts...

Getting the right answer is only half the challenge. Figuring out how to do it quicker and more efficiently, that's where the real fun lies!

I see from your solution to problem 9 that you have also used a conditional auto-indexing output from a for loop. I believe it's more efficient than a build array element, so why not use it again? Knowing that your inputs are integers, why convert to DBL?

Your code takes, on average, 26.3 s to execute on my PC. Getting rid of the build array and the DBL conversion drops the execution to 26.2 s. This may not sound like much gain, but it's a start!

Can you think of ways to get quicker? By far the slowest part of the code is the Mathscript node. There are alternatives out there...

For example, you could use Prime Factor.vi in Mathematics > Elementary > Discrete Math. This will return an array of prime factors for a given input. A prime number only has one prime factor by definition (but 1 is not prime, so must be excluded), so you can check the array size of this output and sum the elements where this size is equal to one. This gets the execution down to 14.3 s on my PC. We've only been doing this for five minutes, but we've already nearly halved the execution time! Woo!

But then why do anything with arrays? Why not just keep a running total of the sum? If the number's prime, I add it to a subtotal kept in a shift register. That drops the execution time by another 20 ms.

But hang on - I know the weak link in my code is still the bit checking whether each integer is prime. I'm still running the same code in every single loop. Presumably, there's a bit of overhead associated with that. What I'd love to do is not run the same code two million times, but run the same code on two million data points.

It turns out that the MathScript isprime function accepts arrays as an input. So I can create an array of integer inputs up to 2000000 beforehand and pass them to isprime(x). The output will now be a 1D Boolean array. So I can use that to determine whether to add the numbers or not in a similar manner to before. Believe it or not, this drops the average execution time on my PC down 1.64 s!

But wait - there's more! Why am I passing an entire array of every number up to 2000000 to it? Why can't I generate a list beforehand of all the numbers up to 2000000 that are obviously not prime - like numbers that end in zero or five? We're now down to 1.53 s execution time... awesome!

Finally, ProjectEuler solutions do not have to be standalone. By that, I mean that you can improve the speed of your code by calculating a list of all the primes up to 2^32 (that's as far as you can go with Mathscript / isprime) beforehand and generating a look-up table of some sort, rather than always repeating that part of the code. For instance, if I want to know the sum of all the primes up to 2000000, I can just cycle through the array of primes in a conditional for loop, checking whether each new prime is less than 2000000. If it is, I can add it to my running total; if not, I stop the loop. Simples.

It's a valid technique, and you'll soon see your solutions getting quicker and quicker as you reuse code/results like this.

Programming invariably gives you a multitude of routes to get things done. If the result's all that matters, then it doesn't matter which route you go down. But you'll find that reworking code to get the same result in less time, in a more supportable/expandable manner, is one of the key tenets of modern software development approaches. Welcome to code refactoring

Congratulations on solving the problem, and keep up the good work.

---
CLA
altenbach
Knight of NI Knight of NI
Knight of NI
on

I posted my version here. It is orders of magitude faster.

It does 2M in under 10ms and 500M in a few seconds. Try it out!

Let me know if you have any questions.