TR Forums

Dim PrimeTest As Double
Dim PrimeDiv As Double
Dim DivValue As Variant
Dim flag As Integer

Sub CalcPrime()

PrimeTest = Range("A2")
PrimeDiv = 0
flag = 0

Do
PrimeTest = PrimeTest + 1

PrimeDivision:
flag = 0
PrimeDiv = 1
While PrimeDiv <= (PrimeTest) / 2
DivValue = PrimeTest / PrimeDiv
If DivValue = 1 Then
flag = flag + 1
    ElseIf DivValue = Int(DivValue) Then
            flag = flag + 1
                ElseIf DivValue = PrimeTest Then
                        flag = flag + 1
    End If
PrimeDiv = PrimeDiv + 1
Wend

If flag = 1 Then GoTo PrimeConfirm
If flag <> 1 Then PrimeTest = PrimeTest + 1
GoTo PrimeDivision

PrimeConfirm:
Range("A2") = PrimeTest
flag = 0
Loop Until 1 > 1 + 1
End Sub

Sub CalcPrime2()

PrimeTest = Range("A2")
PrimeDiv = 0
flag = 0

ArrayLoad

Do
PrimeTest = PrimeTest + 1

PrimeDivision:
flag = 0
ArrayRef = 1
While PrimeArray(ArrayRef) <= (PrimeTest) / 2
DivValue = PrimeTest / PrimeArray(ArrayRef)
If DivValue = 1 Then
flag = flag + 1
    ElseIf DivValue = Int(DivValue) Then
            flag = flag + 1
                ElseIf DivValue = PrimeTest Then
                        flag = flag + 1
    End If
ArrayRef = ArrayRef + 1
Wend

If flag = 1 Then GoTo PrimeConfirm
If flag <> 1 Then PrimeTest = PrimeTest + 1
GoTo PrimeDivision

PrimeConfirm:
Range("A2") = PrimeTest
Cells(ArrayRef, 3) = PrimeTest
flag = 0
Loop Until 1 > 1 + 1
End Sub

Sub ArrayLoad()

Do

PrimeArray(ArrayNumber) = Cells(ArrayNumber, 3)
ArrayNumber = ArrayNumber + 1

Loop Until Cells(ArrayNumber, 3) = 0

End Sub

create an array a with highest subscript n
initialize all elements of a to 0
for each integer i from 2 to square root of n
    if a[i] is 0
        for each integer j from i*2 to n, stepping by i
            set a[j] to 1

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(int argc, char *argv[])
{

    // Make sure user specified upper bound
    if (argc > 1)
    {

        // Get upper bound from command line
        int n = atoi(argv[1]);
        if (n > 0)
        {

            // Allocate array and clear it
            bool *a = new bool[n + 1];
            for (int i = 0; i < n + 1; i++)
                a[i] = false;

            // Find the primes
            int sqrtn = (int) sqrt(n);  // in case compiler is stupid
            for (int i = 2; i <= sqrtn; i++)
            {
                if (!a[i])  // i is prime
                {
                    for (int j = i * 2; j <= n; j += i)
                        a[j] = true;
                }
            }

            // Print them all out
            for (int i = 2; i <= n; i++)
            {
                if (!a[i])
                    printf("%d\n", i);
            }

            // Deallocate the array
            delete [] a;

        }

    }
    else
    {
        printf("please specify highest desired prime\n");
    }

    return 0;

}

'**************************************************************************
'Call routine with the limit of values you wish to find, and a destination
'list box for the values to be shown in.
'example:
'
' findPrimes 10000, frmMain.lstResults
'
' Returns: Nothing.
'
'**************************************************************************
Public Sub findPrimes(upperBound As Long, destList As ListBox)
Dim I, J As Long
Dim a() As Boolean
Dim sqrtn As Long

    destList.Clear                          'Clear the list box

    If upperBound > 0 Then                  'Check the uper bounds value
        ReDim a(upperBound) As Boolean      'Will also empty array to 0, or False.
        
        sqrtn = Sqr(upperBound)             'Find out how far we really need to go, and calc once only
        
        For I = 2 To sqrtn
            If Not a(I) Then                'I is a prime
                J = I * 2
                Do
                    a(J) = True
                    J = J + I
                Loop While J <= upperBound
            End If
        Next I
        
        For I = 2 To upperBound             'Essentially print them all out to the list box.
            If Not a(I) Then destList.AddItem I
        Next I
    Else
        MsgBox "Upper bound must be > 0", vbCritical
    End If
End Sub

//  Sieve of Eratosthenes - packed bit flag version

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// Define a useful type
typedef unsigned char byte;

// Macro SetBit(a, n) sets the nth bit of byte array a
#define SetBit(a, n) ((a)[(n) >> 3] |= (1 << ((n) & 0x7)))

// Macro TestBit(a, n) tests the nth bit of byte array a
#define TestBit(a, n) (((a)[(n) >> 3] & (1 << ((n) & 0x7))) != 0)

int main(int argc, char *argv[])
{

    // Make sure user specified upper bound
    if (argc > 1)
    {

        // Get upper bound from command line
        int n = atoi(argv[1]);
        if (n > 0)
        {

            // Allocate array and clear it
            int alen = (n + 1) / 8 + 1;
            byte *a = new byte[alen];
            for (int i = 0; i < alen; i++)
                a[i] = 0;

            // Find the primes
            int sqrtn = (int) sqrt(n);  // in case compiler is stupid
            for (int i = 2; i <= sqrtn; i++)
            {
                if (!TestBit(a, i))  // i is prime
                {
                    for (int j = i * 2; j <= n; j += i)
                        SetBit(a, j);
                }
            }

            // Print them all out
            for (int i = 2; i <= n; i++)
            {
                if (!TestBit(a, i))
                    printf("%d\n", i);
            }

            // Deallocate the array
            delete [] a;

        }

    }
    else
    {
        printf("please specify highest desired prime\n");
    }

    return 0;

}