Prime Number finder.

[Magix]

Here is a prime number finder. You enter a low number and a high number, and the program can list out for you all the prime numbers between them, and in the end, it outputs the total number of prime numbers. Only problem is that, because of my noob coding and Turing's un-flexibility, it runs very slowly if the gap between the numbers you enter is too big. If you enter 1 and 10,000, it runs just fine, but enter 1 and 100,000, and the thing gets slower. It still works though.

Here is a sample of the output from the program.

code:

Enter starting number (lower number) Starting number: 1 Enter ending number (higher number) Ending number: 100 The program will now calculate how many prime numbers there are... List of prime numbers between 1 and 100... 1 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 There are 26 prime numbers between 1 and 100.

[DemonWasp]

If you want it to go faster, there are better algorithms available...

[Tony]

Magix @ Thu Dec 10, 2009 5:52 pm wrote:

because of ... Turing's un-flexibility

As DemonWasp points out, you are just writing slow algorithms. Turing does have some performance issues that are more apparent, but if you were to write the same code in any other language, it would still be O(n^2) (read "very slow").

Edit: that's not to say that this is a bad start. In fact, this solution is an expected starting point for this problem. I just don't want you to have misconceptions about the tools that you are using.

[Magix]

I've coded with C++ for a couple years and a program with a similar structure can go much, much faster than Turing. I'm too noob to think of a better algorithm. If anybody could help me find a better way...that would be great.

[DtY]

Magix @ Fri Dec 11, 2009 7:29 am wrote:

I've coded with C++ for a couple years and a program with a similar structure can go much, much faster than Turing. I'm too noob to think of a better algorithm. If anybody could help me find a better way...that would be great.

Of course C++ is faster than Turing, but your algorithm would still be really slow in C++. Look at the link DemonWasp posted.
The idea is that you start with an array of booleans representing each number (all set to true at the start). You start at the beginning, and remove all the multiples of two (any multiple of two cannot be prime because one of the factors is two), then you continue with three, and strike out all the multiples of three, then continue to the next number that is still set to true, so you skip four and go to five, and so on.

[Superskull85]

You don't really need to use an array, you could simply check to see which odds value between the low value and high value are prime. You know that if the low value is 1 than both 1 and 2 are prime, and you can print them out. If the low value is 2 you know that 2 is prime so you can print that out. Now you just have to start at 3 and iterate between all odd values from 3 to the high value.

For example:

Turing:

function IsPrime (Num : int) : boolean     result (Num = 3 or Num = 5 or Num = 7) or              (Num mod 3 not= 0 and Num mod 5 not= 0 and Num mod 7 not= 0) end IsPrime function NumPrime (Low, High : int) : int     var Count : int := 0     var TempLow : int := Low     if Low <= High and Low > 0 then         if Low = 1 then             Count += 2             TempLow := 3         elsif Low = 2 then             Count += 1             TempLow := 3         end if         for i : TempLow .. High by 2             if IsPrime (i) then                 Count += 1             end if         end for     end if     result Count end NumPrime proc PutPrime (Low, High : int)     var TempLow : int := Low     if Low <= High and Low > 0 then         if Low = 1 then             put 1             put 2             TempLow := 3         elsif Low = 2 then             put 2             TempLow := 3         end if         for i : TempLow .. High by 2             if IsPrime (i) then                 put i             end if         end for     end if end PutPrime setscreen ("text") put "Number of prime numbers between 1 and 100 are: ", NumPrime (1, 100) PutPrime (1, 100)

[DemonWasp]

In general, a faster algorithm in a slow implementation will tend to dominate over a slower algorithm in a faster implementation for sufficiently large problems. That is, as the number of primes you want to find increases, a faster algorithm in Turing will become increasingly competitive, even surpassing, the slower one written in C/C++.

The sieve I've linked to is way faster than the expected first answer to the problem (what you have). Try finding prime numbers to 1,000,000 or more and that sieve can do it, but the naive implementation will take essentially forever.