New Idea for Prime Number Sieve

[bdonelson]

TL;DR Summary

Prime Number Sieve

I am new to this forum, and I want to see what everyone thought of my idea. I realize that "everyone" has a new idea, but I have not been able to find any references to something similar.


This is an algorithm of a prime sieve, and I am looking for ways to test its accuracy & efficiency. I am open to any suggestions.

--------------------------------------------------------------------------------------------------------------------------------------------------------------

// Starting with the Subset { 6X ± 1 } arranged in pairs (5, 7) (11, 13) (17, 19)  ... ( 6n - 1, 6n + 1)

// Minus_Check, and Plus_Check are indicators of ( Possible Prime ) status, Default Value = Prime

// ----------------------------------------------------------------------------------

N = 1000                                 // Set to Test Range

Max_Multiple = int ( N / 6 )

Stop_Value = sqrt ( Max_Multiple ) + 1

Starting_Side_Flag = 0                            // Side_Flag is an indicator of which side of the 6X±1

Current_Odd_Number = 3

Current_Multiple = 1

First_Step = Current_Odd_Number    

Next_Pair = Current_Multiple + First_Step                // First Multiple to Set Check Value

Loop

    If ( Starting_Side_Flag = 0 )                     // Which Side of the Multiple 

        Then Starting_Side_Flag = 1

        Else  Starting_Side_Flag = 0

    First_Step = Current_Odd_Number                    // First Multiple to Set Check Value

    Second_Step = Current_Multiple * 2                // Second Multiple to Set Check Value

    Current_Pair = Current_Multiple + First_Step            // Goto First Record for Current Possible Prime

    If ( Check = True )                         // Check if Current Value is Marked as Prime

                                    // Inside Loop

        Loop

                                    // First Step

            Goto Record ( Next_Step )

            If ( Side = 0 )

                Set Minus_Check = 0

            Else

                Set Plus_Check = 0

            End If
                                    // Second Step

            Current_Pair = Current_Pair + Second_Step

            Goto Record ( Current_Pair )

            If ( Side = 0 )

                Set Minus_Check = 0

            Else

                Set Plus_Check = 0

            End If


            If ( Side_Flag = 1; 0; 1)


            Exit Loop If ( Current_Pair = Max_Multiple )


            Current_Pair = Current_Pair + First_Step


        End Loop 

                                    // Inside Loop

    If ( Starting_Side_Flag = 1 )

        Current_Multiple = Current_Multiple + 1

    Goto Current_Multiple

    Exit Loop If ( Current_Multiple ≥  Stop_Value )

    Current_Odd_Number = Current_Odd_Number + 2

    If ( Starting_Side_Flag = 1)

        Starting_Side_Flag = 0

    End If                             // Check if Current Value is Marked as Prime

End Loop  

                                // Outside Loop

End


--------------------------------------------------------------------------------------------------------------------------------------------------------------

Any comments would be appreciated.

Thank you.

 

[Baluncore]

Welcome to PF.

What language is it written in ?
Does it run and give sensible results ?

 

[Mark44]

What language is it written in ?

It seems to be more of an algorithm in pseudocode than an implementation in a particular language.

Does it run and give sensible results ?

I don't believe it runs.

A comment for the OP -- You have three lines with Goto statements:

Goto Record ( Next_Step )
Goto Record (Current_Pair)
Goto Current_Multiple

Many programming languages still support goto statements, even though they are somewhat archaic. The syntax for goto in languages that I'm familiar with take the form goto Label, where Label is nothing more than a location in the code. More specifically, a label is not a variable, as Current_Multiple is, nor can a label take parameters; e.g. Record in the first two lines.

As a result, I have no idea what these are supposed to be doing, and I'm not aware of languages in which these lines would be allowed.

 

[PeterDonis]

I have not been able to find any references to something similar.

You haven't been able to find any references to algorithms for a prime number sieve? I find that hard to believe. Where have you looked?

 

[Filip Larsen]

A few comments:
Looks like a simple iterative algorithm with no discernible output (at what point in the algorithm do you believe a variable is holding a prime?).

It does not look like a sieve, but more like a generated table of selected (possible) primes. I do not recognize any step that allows you to conclude that a possible prime is a prime.

The "trick" of generating (possible) primes by skipping all even numbers (and similar) is well-known. A simple sieve would probably just skip the even numbers. It looks like this algorithm tries to skip 6 at a time. If generation is all that matters there are other generators that might be more useful.

You may also want to read up on various computational methods for primes.

 

[Baluncore]

I have trouble identifying the structure of the program.

Also, I believe there needs to be an array of data somewhere.

Does "Goto record ( Next_Step )" call a procedure called record, or write data to an array or file called record, or go to another line of code or a label.

 

[Mark44]

Does "Goto record ( Next_Step )" call a procedure called record, or write data to an array or file called record, or go to another line of code or a label.

That was a question I had and raised in my previous post.

 

[bdonelson]

Welcome to PF.

What language is it written in ?
Does it run and give sensible results ?

Hi,

You haven't been able to find any references to algorithms for a prime number sieve? I find that hard to believe. Where have you looked?

Not to sound arrogant, but I was refering to searching for something similar to this algorithm. I believe this is that different of a process. Again, I hope that I am not sounding arrogant. Everything I have tested so far has validated the pattern.

It seems to be more of an algorithm in pseudocode than an implementation in a particular language.

I wrote the original test in Filemaker. I tested it out to Primes equal to 100,000.

My post includes the psuedocode, because I was attempting to represent the idea.
The Inner loop was comprised of four steps, Goto a specific record, Set a field as false, Goto another specific record, Set a field as false.
The Outer Loop simply sets one flag, advances two fields, and sets two fields.

I do not recognize any step that allows you to conclude that a possible prime is a prime.

I believe the pattern I found does accomplish that.

It looks like this algorithm tries to skip 6 at a time.

It is based on a pattern that I found that every member of the set { 6X-1 U 6X+1 } appears to follow.

I am currently writing it in C++

This is what I have so far.

#include <stdio.h>
#include <l_list.h>
 
int main()
{

// Starting with the Subset ( 6X ± 1 ) arranged in pairs (5, 7) (11, 13) (17, 19)  ... ( 6n - 1, 6n + 1)

// Minus_Check, and Plus_Check are indicators of ( Possible Prime ) status, Default Value = Prime

// ----------------------------------------------------------------------------------

long N;                                                // Set to Test Range
long MaxMultiple;
long i;
long StopValue;
bool StartingSideFlag;                       // Side_Flag is an indicator of which side of the 6X±1
bool SideFlag  
int CurrentOddNumber;
long CurrentMultiple;
long FirstStep;                                  // First Multiple to Set Check Value
long NextStep;
long CurrentStep;
bool Inside;                                      // Flag for the Inside Loop
bool Outside;                                   // Flag for the Outside Loop

long Minus;                                      // Current (6X-1) Value
long Plus;                                         // Current (6X+1) Value



// ----------------------------------------------------------------------------------

N = 1000;

MaxMultiple = int ( N / 6 );


// Create the List of the Values of the Set of (6X-1) U (6X+1) to the Size N

List.insertAtHead(MaxMultiple);

StopValue = sqrt(MaxMultiple) + 1;

StartingSideFlag = 0;
SideFlag = 0;
CurrentOddNumber = 3;
CurrentMultiple = 1;
FirstStep = CurrentOddNumber;
NextStep = CurrentMultiple + FirstStep;
Inside = True;
Outside = True;


List.FirstRecord()                                                                                  // Goto Beginning of List

While Outside
{                                                                                                           // Outside Loop
    If ( StartingSideFlag = 0)                                                          // Which Side of the Multiple
         SideFlag = 0;
    Else
         SideFlag = 1;

    FirstStep = CurrentOddNumber;                                                     // First Multiple to Set Check Value
    SecondStep = CurrentMultiple * 2;                                                 // Second Multiple to Set Check Value

    List.AdvanceRecords(CurrentMultiple);                                           // Goto First Record for Current Possible Prime

    If( CheckCurrentStatus(StartingSideFlag) )                                     // Check if Current Value is Marked as Prime
    {
        While Inside                                                                                // Inside Loop
        {
            List.AdvanceRecords(FirstStep);                                             // First Step

            If(Side = 0)
                List.MCheck();                                                                   // Set the Psuedo-Prime Flag for the Minus
            Else
                List.PCheck();                                                                   // Set the Psuedo-Prime Flag for the Plus

            List.AdvanceRecords(SecondStep)                                     // Second Step

            If ( SideFlag = 1)
                SideFlag = 0;
            Else
                SideFlag = 1;

            If(Side = 0)
                List.MCheck();                                                                   // Set the Psuedo-Prime Flag for the Minus
            Else
                List.PCheck();                                                                   // Set the Psuedo-Prime Flag for the Plus

            If ( SideFlag = 1)
                SideFlag = 0;
            Else
                SideFlag = 1;

            If ( CurrentStep <= MaxMultiple )
                CurrentStep = CurrentStep + FirstStep + SecondStep;
            Else
                Inside = False;
        }                                                                                                    // Inside Loop
                                

    If ( StartingSideFlag = 1 )
        CurrentMultiple = CurrentMultiple + 1;

    List.FirstRecord()

    If ( CurrentMultiple <= StopValue )
    {   
        CurrentOddNumber = CurrentOddNumber + 2;

        If(StartingSideFlag = 1)
           StartingSideFlag = 0
    }
    Else
        Outside = False

    }                                                                                                      // Check if Current Value is Marked as Prime

}                                                                                                         // Outside Loop

// Show List of Primes

List.print();

}

Hopefully, this is easier to follow.

I am finishing the setup of the linked list structure that looks like this:

    long Multiple;             // Multiple of 6.  The basis of the data structure.
    long Minus;                // Current Multiple - 1
    long Plus;                   // Current Multiple + 1
    bool M_Check;           // Is the value Minus still a Prime Possible
    bool P_Check;            // Is the value Plus still a Prime Possible 
    Node *next;

My next step is to test it to larger values.

At what point does one decide it is time to seek out computing resources capable of testing the large value that Prime Numbers currently using?

 

[PeterDonis]

I was refering to searching for something similar to this algorithm

Are you familiar with the algorithms that already exist? If not, you should be.

I believe this is that different of a process.

How do you know that if you don't know what algorithms already exist?

I hope that I am not sounding arrogant

The word I would use based on what I've seen so far is "uninformed".

 

[Filip Larsen]

I wrote the original test in Filemaker. I tested it out to Primes equal to 100,000.

I guess that is the Claris Filemaker DBMS tool then and your first code is a Filemaker script. Which kind of explains the weird structure and that "Goto Record" do not really mean what most of us here probably thought it meant, but instead (I assume) is part of getting data into the result table.

If you manage to make minimum workable version in a more traditional language (you mention you will try aim for C++), then that may up the chance that someone here may be able to make more sense of what you are trying to do. But please make it run correctly first as there is little point in showing us pseudo code that is a mix of C++ and Filemake scripting.

As an example after a quick search, here is a very simple runnable C++ sieve: https://onecompiler.com/cpp/3x9dj68ad
There are a number of online compilers and environments for almost any general language you'd like, so it may be beneficial to try make your version runnable on one of those.

 

[bdonelson]

If you manage to make minimum workable version in a more traditional language (you mention you will try aim for C++), then that may up the chance that someone here may be able to make more sense of what you are trying to do. But please make it run correctly first as there is little point in showing us pseudo code that is a mix of C++ and Filemake scripting.

As an example after a quick search, here is a very simple runnable C++ sieve: https://onecompiler.com/cpp/3x9dj68ad
There are a number of online compilers and environments for almost any general language you'd like, so it may be beneficial to try make your version runnable on one of those.

Thank you for the link to OneCompiler. This should be useful.

I would to comment here that apparently most people here do not appear to understand the concept of psuedo code. I have seen examples of people that didn't recognize it to begin with.

I think the Wikipedia listing is fairly accurate.

In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actions and conditions.

 

[bdonelson]

The word I would use based on what I've seen so far is "uninformed".

Can you show me one sieve algorithm that is this simple, and appears to be valid out to a value of 100,000?

 

[PeterDonis]

I would to comment here that apparently most people here do not appear to understand the concept of psuedo code

I don't think it's not understanding the concept, it's more a question of whether pseudocode is really the best way to describe an algorithm.

The advantage of giving code in an actual programming language with an actual working implementation is that you can actually run the code and see if it does what it's supposed to do. You can't do that with pseudocode.

 

[PeterDonis]

Can you show me one sieve algorithm that is this simple, and appears to be valid out to a value of 100,000?

You mean you don't already know of any?

Again, are you aware of the sieve algorithms that already exist? Have you looked at any?

 

[bdonelson]

I don't think it's not understanding the concept, it's more a question of whether pseudocode is really the best way to describe an algorithm.

The advantage of giving code in an actual programming language with an actual working implementation is that you can actually run the code and see if it does what it's supposed to do. You can't do that with pseudocode.

To put it simply, pseudocode is to share an idea.

 

[bdonelson]

You mean you don't already know of any?

Again, are you aware of the sieve algorithms that already exist? Have you looked at any?

Let me rephrase this. Do you have any concept of what I am attempting to discuss here?

 

[PeterDonis]

To put it simply, pseudocode is to share an idea.

I never said it wasn't. My point is, is it the best way to share this kind of idea?

You say you've actually run this algorithm. Obviously you didn't run the pseudocode. What code did you actually run?

 

[bdonelson]

I never said it wasn't. My point is, is it the best way to share this kind of idea?

You say you've actually run this algorithm. Obviously you didn't run the pseudocode. What code did you actually run?

I have tested the algorithm using filemaker, so I could focus on the algorithm.

 

[PeterDonis]

Let me rephrase this. Do you have any concept of what I am attempting to discuss here?

Let me rephrase my response: are you going to actually answer the question of what existing knowledge in this subject area you've actually looked at, or are you going to continue to avoid it?

The reason I ask is that you're asking people to spend time and effort figuring out how your algorithm works. Asking people to do that without giving us any information about your knowledge of the subject is asking a lot.

 

[PeterDonis]

I have tested the algorithm using filemaker, so I could focus on the algorithm.

So where's the actual Filemaker code you're running?

 

[bdonelson]

Let me rephrase my response: are you going to actually answer the question of what existing knowledge in this subject area you've actually looked at, or are you going to continue to avoid it?

The reason I ask is that you're asking people to spend time and effort figuring out how your algorithm works. Asking people to do that without giving us any information about your knowledge of the subject is asking a lot.

My whole purpose in starting this post was to discuss a concept. If you are not interested. Why should I care?

 

[PeterDonis]

My whole purpose in starting this post was to discuss a concept.

How do we know it's a concept worth discussing?

If you are not interested. Why should I care?

Part of my job as a moderator is to maintain the signal to noise ratio of these forums, and to enforce the rules. We have rules here against discussing personal research. When we encounter someone who claims to have a better solution to an age-old problem than any of the existing ones, but who knows nothing about the existing ones, our moderator alarm bells for "low signal to noise" and "personal research" start to ring.

 

[bdonelson]

How do we know it's a concept worth discussing?


Part of my job as a moderator is to maintain the signal to noise ratio of these forums, and to enforce the rules. We have rules here against discussing personal research. When we encounter someone who claims to have a better solution to an age-old problem than any of the existing ones, but who knows nothing about the existing ones, our moderator alarm bells for "low signal to noise" and "personal research" start to ring.

Ok, fine. The problem I have is that I asked simply question about very simple idea, Four step algorithm.
As I said I have spent the last 6 months looking for something that is this simple that does this accomplishes. I have discussed this with other mathematicians, and they agreed that the idea works. I am looking for someone who has the Number Theory background to simply take a couple of minutes, and give me there opinion about my idea.
If this is wrong place, I will be happy to leave.

 

[Baluncore]

@bdonelson I am interested in your algorithm. Unfortunately, your pseudocode was insufficient to document your algorithm. I will have to wait until you produce something more complete that I can understand.

 

[bdonelson]

@bdonelson I am interested in your algorithm. Unfortunately, your pseudocode was insufficient to document your algorithm. I will have to wait until you produce something more complete that I can understand.

Thank you for response, I will happy to break it down.

The sieve is a process of taking a value from the set { 6x-1 U 6X+1 }, (5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37 ... N ). Using that value as a starting point to move through the same of numbers, based a simple pattern that I have found, to mark / eliminate the non-primes. Repeating the process for all the primes.

The process using the multiple of 6, a pattern of the odd numbers, & an alternating switch to indentify members of the set to be marked as non-prime.

The steps of this process are

Goto the starting value

Inside Loop
Add to the multiple the First Constant to the Starting Value and choose the Minus or Plus to set based on the alternating switch.
Add to the multiple the Second Constant to the Starting Value and choose the Minus or Plus set based on the alternating switch.
Repeat

The Outside Loop simply sets the First Constant and Second Constant.

I hope this simpler algorithm is easier to follow.

 

[Filip Larsen]

Can you show me one sieve algorithm that is this simple, and appears to be valid out to a value of 100,000?

I gave an example in post #10 with the link to a very simple example (not mine though). Another example that runs, but now slightly more involved using the obvious odd number optimization could be something like listed below. It took me less than 10 min to make this just now, just to indicate that is does not take a huge effort to present a working example and others can then reason about the code very accurately and point out mistakes or suggest improvements.

// C++20
#include <iostream>
#include <vector>

int main()
{
    // Simple prime sieve algorithm checking only the odds numbers
    const size_t N = 1000;  // Maximum prime desired
    const size_t M = N/2-1; // We need this many positions in the sieve
    std::cout<<"List of primes below " << N << ":\n2 ";
    std::vector<bool> composite(M);
    size_t np = 1; // Count how many found (start with 1 to include prime 2)
    for (size_t i = 0, p = 3; i < M; ++i, p += 2) {
        if (!composite[i]) {
            ++np;
            std::cout << p << " ";
            for (size_t j = i; j < M; j += p) {
                composite[j] = true;
            }
        }
    }
    std::cout << "\nTotal number found: " << np << std::endl;

    return 0;
}

 

[bdonelson]

I gave an example in post #10 with the link to a very simple example (not mine though). Another example that runs, but now slightly more involved using the obvious odd number optimization could be something like listed below. It took me less than 10 min to make this just now, just to indicate that is does not take a huge effort to present a working example and others can then reason about the code very accurately and point out mistakes or suggest improvements.

// C++20
#include <iostream>
#include <vector>

int main()
{
    // Simple prime sieve algorithm checking only the odds numbers
    const size_t N = 1000;  // Maximum prime desired
    const size_t M = N/2-1; // We need this many positions in the sieve
    std::cout<<"List of primes below " << N << ":\n2 ";
    std::vector<bool> composite(M);
    size_t np = 1; // Count how many found (start with 1 to include prime 2)
    for (size_t i = 0, p = 3; i < M; ++i, p += 2) {
        if (!composite[i]) {
            ++np;
            std::cout << p << " ";
            for (size_t j = i; j < M; j += p) {
                composite[j] = true;
            }
        }
    }
    std::cout << "\nTotal number found: " << np << std::endl;

    return 0;
}

Ok, I have seen not this one.

The main difference is that it focuses on the odd numbers and I have no need for a complicated loop.

 

[Baluncore]

I hope this simpler algorithm is easier to follow.

Well, not really. Unfortunately, you know exactly what you mean, while I do not, so an abbreviated human language algorithm will not let me know exactly what you intended. I can still see a huge number of possibilities that you have not ruled out. I need a rigorously structured code and some idea of the data structure, or storage you propose. The keyword 'goto' is misleading without a label. It would be better to use a Do ... Loop with conditions.

I have seen many prime finder algorithms and sieves. The 6±1 template gives a small speed-up, and highlights the prime pairs. There are much larger templates that cycle through more sparse step tables.

I believe sieves must start at the beginning, so they take time to build up to reach bigger numbers. Can you start your sieve at an arbitrarily large number and sieve forwards, for primes over a short, yet distant, interval?

Please write your algorithm in a language you can run and test. When it works as intended, post that code in that language, here.

Your initial pseudocode was unnecessarily voluminous.
As an example:

If ( Starting_Side_Flag = 0 )
Then Starting_Side_Flag = 1
Else Starting_Side_Flag = 0

Branching like that flushes the prefetch pipeline in the processor.
Why not toggle the flag bit by using a single integer operation on a single location, such as:
Starting_Side_Flag = 1 - Starting_Side_Flag.

 

[Filip Larsen]

The main difference is that it focuses on the odd numbers and I have no need for a complicated loop.

First, I think you are just dodging the issue. We asked for a working version of your algorithm and you then ask for an example of what that mean and then just seem to dig yourself deeper into explanations that are even less workable/verifiable.

Second, my example, like most simple sieves or primality computational methods that generates the exact list of primes below N needs at least what corresponds to two nested loops thus making the run-time complexity O(N²) or O(N^3/2) at best (more complicated methods may do better). If you claim your algorithm can generate an exact list of primes below N in complexity O(N) then you are (as far as I know) making a rather wild claim.

Edit: I can see that Sieve of Atkin (from 2003) actually manage to achieve O(N) complexity, but (as I understand) has so large a complexity constant that other methods with higher complexity, e.g. O(N log log N), may actually run faster for very large values of N.

 

[PeterDonis]

very simple idea

The fact that three posters in this thread so far have failed to understand your description of your algorithm indicates that it's not as simple as you seem to think.

 

[bdonelson]

Ok, that does sound like a good idea. Thank you.

Maybe this is closer to what you asking for?

Here is the center of the algorithm.

// FirstStep is set to a value based on the Current Multiple of 6 Managed in the Outer Loop ( 6, 12, 18, etc. )
// SecondStep is set to a value based on the Current Odd Number ( 3, 5, 7, 9, 11, 13, 15, etc )

While (Inside = True)                                                       // Inside Loop

        {
            List.AdvanceRecords(FirstStep);                           // Advance to the next Value based on FirstStep

            If(Side = 0)
                List.MCheck();                                                   // Set the Non-Prime Flag for the Minus
            Else
                List.PCheck();                                                    // Set the Non-Prime Flag for the Plus

            List.AdvanceRecords(SecondStep)                     // Advance to the next Value based on SecondStep

            If ( SideFlag = 1)                                                // SideFlag Switches
                SideFlag = 0;
            Else
                SideFlag = 1;

            If(Side = 0)
                List.MCheck();                                                  // Set the Non-Prime Flag for the Minus
            Else
                List.PCheck();                                                   // Set the Non-Prime Flag for the Plus


            If ( SideFlag = 1)                                                 // SideFlag Switches
                SideFlag = 0;
            Else
                SideFlag = 1;

            If ( CurrentStep <= MaxMultiple )                     // MaxMultiple = Maximum Prime Value / 6

                CurrentStep = CurrentStep + FirstStep + SecondStep;    // Tracking Which Prime is Used

            Else

                Inside = False;

        }                                                                   // Inside Loop

Is this easier to follow?

 

[Baluncore]

Is this easier to follow?

Did you run it, and get a correct result?

 

[bdonelson]

Apparently, no one understands to think. Why did I waste my time. Goodbye

 

[Filip Larsen]

Did you run it, and get a correct result?

I think the OP indirectly just answered that.

 

[Baluncore]

Why did I waste my time.

You failed to clearly communicate your algorithm. You only needed to code your algorithm, run it, and prove it once. It would then have been possible for us to compare that to other algorithms. You actually wasted our time.

 

[PeterDonis]

Apparently, no one understands to think. Why did I waste my time. Goodbye

Thread closed.

 

[Mark44]

I would to comment here that apparently most people here do not appear to understand the concept of psuedo code. I have seen examples of people that didn't recognize it to begin with.

I beg to differ. I'd be willing to bet that all of the people responding here are very familiar with the concept of pseudocode. Speaking for myself, I taught a variety of programming languages, at least six or seven of them, over a course of about 20 years. Pseudocode was an important part of all of these classes.

In computer science, pseudocode is a description of the steps in an algorithm using a mix of conventions of programming languages (like assignment operator, conditional operator, loop) with informal, usually self-explanatory, notation of actions and conditions.

We're all very familiar with these concepts. What was confusing to myself and others was your unusual use of goto statements.

Thread is still closed.