primenumber

Example 1

Now we will explain the task.

Primes are products of two numbers. In other words, a prime is divisible only by itself or 1. So, calculating primes by means of "The Sieve of Eratosthenes" is done like this:

We start with a list of candidates containing numbers from 2 to the definite number. 2 is a prime. We remove all even numbers from the list. Now, we will take 3 and remove all the numbers that are products of it. After this, we find the next number from the candidate list. This number is 5, then we remove the fifth numbers from the list, etc. Therefore, when the candidate list is empty, the result list will contain all the primes.

Let's break the problem into two steps. The first step takes advantage of the algorithm, and the second step outputs the results to the screen.

str   input
uint  high i j

print("This program uses \"The Sieve of Eratosthenes\" for finding prime numbers.\n\n")
high = uint( congetstr("Enter the high limit number ( < 100000 ): ", input ))
if high > 100000 : high = 100000

arr  sieve[ high + 1 ] of byte

fornum i = 2, high/2 + 1
{
   if !sieve[ i ]
   {
      j = i + i
      while j <= high
      {
         sieve[ j ] = 1
         j += i
      }
   }
}

To begin with, a user should enter the number which is defined as the final candidate in the list. We want all primes below 100000 in order to not use a lot of resources.

arr  sieve[ high + 1 ] of byte

sieve is a description of an array of bytes. And array is a series of objects, all of which are the same size and type. Each object in an array is called an array element. For example, you could have an array of integers or an array of characters or an array of anything that has a defined data type. The important characteristics of an array are that (1) Each element has the same data type (although they may have different values). (2) The entire array is stored contiguously in memory.

The first element in the array is the 0th element, therefore let's set 1 to this number. Actually, arrays and variables are zero-based. So, if an element of the array equals 0, then this based number is not removed. If we remove it, we'll set 1 to this number.

For the fornum loop we use only half of the numbers. Why do we do this? Think it over. Then we apply the algorithm. As you can see, it takes up several strings. Let us jump into an example that illustrates how it works:

j += i

This is an extension of the j variable to i. Similar operations are applied for the multiplication, the division, the subtraction.

The numbers has already been removed; let's now jump to the second step.
It is certainly possible that the numbers are output to the screen, nevertheless let's save a file.

j = 0
input.setlen( 0 )

fornum i = 2, high + 1
{
   if !sieve[ i ]
   {
      input.out4( "%8u", i )
      if ++j == 10 
      {
         j = 0
         input += "\l"
      }
   }
}

input.write( "prime.txt" )
shell( "prime.txt" )

To find out more about the out4 method, read the documentation. In this case each number is extended to eight symbols by spaces. Furthermore, after outputting each tenth number we start a new line. The j variable performs it.

A combination of carriage return '\r' and newline '\n' is used for line feed in text files. In Gentee there's only '\l' command which executes it.

The write method writes the string to the file, and the function shell opens this specified file in the appropriate application.

Source

• samples/primenumber/eratosthenes.1.g