27652

Optimize calculation of prime numbers [duplicate]

Question:

This question already has an answer here:

<ul><li> <a href="/questions/8176928/project-euler-3-highest-prime-factor" dir="ltr" rel="nofollow">Project Euler 3 - Highest Prime Factor</a> <span class="question-originals-answer-count"> 2 answers </span> </li> <li> <a href="/questions/12025378/project-euler-3-takes-forever-in-java" dir="ltr" rel="nofollow">Project Euler #3 takes forever in Java</a> <span class="question-originals-answer-count"> 9 answers </span> </li> </ul>

I am trying <a href="https://projecteuler.net/problem=3" rel="nofollow">Problem 3</a> from Project Euler and my algorithm is far too slow. Does anyone know how to optimize this? The number I am trying to calculate up to is 600851475143L. It takes forever to calculate this so I need a way to speed up the calculations.

LOGIC:

<ul><li>Go through all the numbers from 3 until that number-1</li> <li>For each of these numbers check if they are prime by dividing them by all the numbers in between and if they dont divide by any of them then they are prime.</li> <li>

If prime then add them to an array.

public static void problem3(long number){ long number2 = number; long sqrtNumber = (long)Math.sqrt(number2); int indexNum = 1; boolean isPrime = false; int primeNums[] = new int[2]; primeNums[0] = 2; //puts prime numbers into an array for(int y = 3; y < sqrtNumber; y++){ isPrime=true; for(int theNum = 2; theNum < y; theNum++){ //if y divides evenly by any number then it is not prime if(y%theNum==0){ //dont store in array isPrime=false; break; } } if(isPrime == true){ //add to array System.out.println(y); //put y in the array and exapnd the array //System.out.println("y: " + y); primeNums[indexNum] = y; int[] newArray = new int[primeNums.length + 1]; System.arraycopy(primeNums, 0, newArray, 0, primeNums.length); primeNums = newArray; indexNum++; } } </li> </ul>

********** UPDATE **************

I calculated up to the square root which sped up the calculations a lot but I also done something else which was to add a break statement in the forloop to break once I discovered the number was not prime. I edited the code above to reflect these changes.

My algorithm is still wrong for calculating the prime factors though so I will need to have a look at it and maybe raise a new question.

<hr />

Answer1:

You don't have to divide by every number. You only have to divide by each prime number between 2 and the square root of your number.

Answer2:

The first thing you can do is only test possible factors up through the square root of the number that you're testing, because if you find a factor greater than the square root, then you should have found a factor less than the square root.

If you need additional performance, then use the <a href="http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes" rel="nofollow">Sieve of Eratosthenes</a>. That allows you to use the results of previous primes to cut down the work on determining if larger numbers are prime.

Recommend

  • Java ProcessBuilder Cannot Find File Specified
  • My Python number guessing game
  • how to convert a unix timestamp into nsdate in iphone [duplicate]
  • interpolation in 3d computer graphics
  • Count the occurrences across multiple columns
  • How to use arithmetic operators with SAS macro variables [duplicate]
  • Retrieving a double from a JTextArea while solving for X
  • Deduce parent class of inherited method in C++
  • Hide HTML elements without javascript, only CSS
  • Problems compiling files using JOGL
  • Parsing a CSV string while ignoring commas inside the individual columns
  • Transactional Create with Validation in ServiceStack Redis Client
  • Swing - Get new component under mouseReleased
  • Content-Length header not returned from Pylons response
  • MVC3 Razor - ListBox pre-select not working
  • Play WS (2.2.1): post/put large request
  • Set the selected item in dropdownlist in MVC3
  • How to access EntityManager inside Entity class in EJB3
  • ilmerge with a PFX file
  • Spring Data JPA custom method causing PropertyReferenceException
  • Splitting given String into two variables - php
  • Can I display google adwords (AdView) in javafx on android
  • req.body is undefined - nodejs
  • Validaiting emails with Net.Mail MailAddress
  • sending/ receiving email in Java
  • vba code to select only visible cells in specific column except heading
  • VB.net deserialize, JSON Conversion from type 'Dictionary(Of String,Object)' to type '
  • Cannot Parse HTML Data Using Android / JSOUP
  • How to delete a row from a dynamic generate table using jquery?
  • Proper way to use connect-multiparty with express.js?
  • JTable with a ScrollPane misbehaving
  • Angular 2 constructor injection vs direct access
  • Java static initializers and reflection
  • Android Google Maps API OnLocationChanged only called once
  • unknown Exception android
  • EntityFramework adding new object to nested object collection
  • Checking variable from a different class in C#
  • failed to connect to specific WiFi in android programmatically
  • UserPrincipal.Current returns apppool on IIS
  • How can I use threading to 'tick' a timer to be accessed by other threads?