Method for generating prime numbers

Page 4 of 8 [ 113 posts ] Go to page Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Previous topic | Next topic

NeantHumain
Veteran
Veteran

Joined: 24 Jun 2004
Age: 46
Gender: Male
Posts: 4,837
Location: St. Louis, Missouri

15 Feb 2012, 11:20 pm

blahblah123 wrote:

I found an O(n) time algorithm to generate the first n prime numbers. I've already sent it to the NSA.

C++ code:

Code:

#include<iostream>
using namespace std;

int main()
{
      int n;
      cin >> n;
      for(int i = 0; i < n; i++)
      {
            print_prime(i);
      }

     return 0;
}

This is assuming print_prime(i) runs in O(1) time.

Guys, please don't steal my work.

How's that going to compile? The function print_prime(int) isn't defined in iostream. In other words, where's the algorithm?

Ancalagon
Veteran
Veteran

Joined: 25 Dec 2007
Age: 47
Gender: Male
Posts: 2,302

16 Feb 2012, 12:12 am

NeantHumain wrote:

Ha, anyway if we're talking optimizations, one thing is to substitute an equivalent iterative algorithm in place of the recursive one. The recursive algorithm runs the risk of a stack overflow for larger numbers, not to mention the overhead of calling a function, pushing its arguments onto the stack, etc.

There is a compiler optimization called tail recursion that would generate the code for the iterative version given the recursive one. I know gcc supports it, although I don't know about other C compilers.

You have to set up your recursion to pass all the information the next iteration needs as arguments, but IIRC you actually did that the first time around.

_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Declension
Veteran
Veteran

Joined: 20 Jan 2012
Age: 38
Gender: Male
Posts: 1,807

16 Feb 2012, 12:17 am

NeantHumain wrote:

How's that going to compile? The function print_prime(int) isn't defined in iostream. In other words, where's the algorithm?

Geez, tough crowd.

I guess it's always going to be awkward to make such a joke in a community well-known for being bad at understanding subtext... Is it being a jerk to make a non-obvious joke here, knowing that a lot of people won't get it? Or does it help to "train" people to spot jokes? This is something that I have been wondering ever since that "Marxist professor" thread.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 71
Gender: Male
Posts: 116
Location: Missoula, MT

16 Feb 2012, 1:07 am

Declension wrote:

jackmt wrote:

Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship.

I don't mean to be rude, but are you sure that you're not becoming a crank?

http://en.wikipedia.org/wiki/Crank_(person)

The idea that you have found a method for generating primes that is better than any method that has ever been found, given that you have not trained as a mathematician, is bordering on "impossible". In fact, I would go even further and say that it actually is impossible. So much work has been put into this problem that any improvement would take at least fifty pages to write down. If your method is written on a couple of pages... there's something wrong with it. There just is.

Comments that you have made seem to indicate that you are no closer to generating primes than you ever were. You have a method that generates numbers that are "either primes or products of primes". That includes every single natural number greater than 1. It's not an achievement at all.

You may be right, but I don't think so. I'll work on it again and get back to you.

NeantHumain
Veteran
Veteran

Joined: 24 Jun 2004
Age: 46
Gender: Male
Posts: 4,837
Location: St. Louis, Missouri

16 Feb 2012, 10:16 am

Ancalagon wrote:

NeantHumain wrote:

Well, we're assuming an optimizing compiler, and I know at least the older Microsoft Visual C++ compilers in their "Standard Edition" or "Learning Edition" (perhaps now "Express Edition") did not include an optimizing C or C++ compiler.

Shorttail
Blue Jay

Joined: 3 Feb 2012
Age: 40
Gender: Male
Posts: 95
Location: Aarhus, Denmark

16 Feb 2012, 12:07 pm

Declension wrote:

Pffft. That's nothing. I just sent the NSA an O(n) algorithm that generates all of the first n natural numbers, not just the primes. Your method has been made redundant.

Thanks. I mean, the NSA says thanks. Of course.

blahblah123 wrote:

Guys, please don't steal my work.

Reminds me of my master code that produces all positive integers in O(n) time.

jackmt wrote:

You may be right, but I don't think so. I'll work on it again and get back to you.

I definitely want to hear how it goes. :3

Declension wrote:

If you want a shoulder pat, try post it on stack overflow. ;3

Thom_Fuleri
Veteran
Veteran

Joined: 7 Mar 2010
Age: 47
Gender: Male
Posts: 849
Location: Leicestershire, UK

18 Feb 2012, 8:00 pm

jackmt wrote:

I have devised a method for generating prime numbers. Is there one already in existence?

Since you're not telling us anything about this magical algorithm, we're entirely unable to assess it. But I do have an interesting question. You've already said that it returns both primes and multiples of primes, and these need weeding out - the big question I have is whether it returns ALL the primes in a given range? Or just some of them?

I mean, I think 7420738134811 is a prime number. If it isn't, it's a multiple of one. But I couldn't tell you whether there were any more in the vicinity.

(Actually, aren't all numbers multiples of primes?)

ruveyn
Veteran
Veteran

Joined: 21 Sep 2008
Age: 89
Gender: Male
Posts: 31,502
Location: New Jersey

18 Feb 2012, 8:30 pm

Is there a computable function F such that F(n) is the n-th prime?

F(1) = 2
F(2) = 3
F(3) = 5
and so on.

ruveyn

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 71
Gender: Male
Posts: 116
Location: Missoula, MT

18 Feb 2012, 9:27 pm

Thom_Fuleri wrote:

jackmt wrote:

I have devised a method for generating prime numbers. Is there one already in existence?

It generates only primes larger than 7, and it appears to generate all such primes. It also appears I was prematurely optimistic about its limited production of products of primes (not multiples of primes). It is producing more than I expected.

jackmt
Raven
Raven

Joined: 13 Dec 2011
Age: 71
Gender: Male
Posts: 116
Location: Missoula, MT

18 Feb 2012, 9:34 pm

jackmt wrote:

Declension wrote:

jackmt wrote:

Thank you. And that is why I'm reluctant to show it. I've already had one of my papers stolen after being assured that my work being the earliest was enough proof of authorship.

You may be right, but I don't think so. I'll work on it again and get back to you.

Added 2:18 [oops. I thought I was editing]

I appreciate your skepticism. When I discovered it I was just playing with primes, discovered a set of properties, and imported a little trick I had invented from arithmetic to maintain that set of properties while changing the number. It is really that simple.

I didn't think I had discovered anything great. I thought surely someone else had found the same thing. Same mistake I made with my stolen paper on the Fibonacci sequence. Same method of discovery, as well. "Life is frittered away with detail. Simplify. Simplify." Thoreau

I am not your usual analyst. My methods always seek to simplify the problem, not find a more complex way to solve it. Being an Aspie, I tend to notice patterns, then I exploit them.

I don't know how to write a program to run it, but I think that would be rather simple.
All numbers are primes, sums of primes, or products of primes. My method generates primes greater than 7, and only products of primes larger than 5. More than I anticipated, but fewer than all.

More later.

Last edited by jackmt on 18 Feb 2012, 10:26 pm, edited 2 times in total.

Ancalagon
Veteran
Veteran

Joined: 25 Dec 2007
Age: 47
Gender: Male
Posts: 2,302

18 Feb 2012, 10:08 pm

ruveyn wrote:

Is there a computable function F such that F(n) is the n-th prime?

F(1) = 2
F(2) = 3
F(3) = 5
and so on.

ruveyn

F(n) = if (n=1) then 2 else X(F(n-1)+1)

X(n) = if (P(n) = 1) then n else X(n+1)

P(n) = if (D(n-1, n) = 0) then 1 else 0

D(i, n) = if (i <= 1) then 0 else (if (i | n) then 1 else D(i-1, n))

D(i, n) returns 1 when some number greater than 1 and less than or equal to i divides n.
P(n) returns 1 if n is prime.
X(n) returns the smallest prime equal to or greater than n.
F(n) returns the nth prime number.

Not fast at all, but computable.

_________________
"A dead thing can go with the stream, but only a living thing can go against it." --G. K. Chesterton

Thom_Fuleri
Veteran
Veteran

Joined: 7 Mar 2010
Age: 47
Gender: Male
Posts: 849
Location: Leicestershire, UK

19 Feb 2012, 5:05 am

An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
A little algebra, however, soon explains why.

6n is not prime (divides by 6!)
6n+2 and 6n+4 (or 6n-2) divide by 2.
6n+3 (or 6n-3) divides by 3.
So any prime necessarily much be one of the two remaining options - 6n+1, or 6n+5 (6n-1).

heavenlyabyss
Veteran
Veteran

Joined: 9 Sep 2011
Gender: Male
Posts: 1,393

19 Feb 2012, 5:06 am

Umm, I would like to see this algorithm explicitly, I would be very fasincated to see it actually.

In my highschool years, I found a book that my dad had that listed prime numbers up to about 10,000 or so, and I became very fascinated with it, trying to find the pattern in the whole. I vehemently disagree with this common conception that is random. I always felt like there must be some underlying chatoic pattern to the primes. I mean, how could be there not be?

I do think an Indian mathematician came up with a pretty good method. I will look up and report on it afterward.

heavenlyabyss
Veteran
Veteran

Joined: 9 Sep 2011
Gender: Male
Posts: 1,393

19 Feb 2012, 5:49 am

Okay, the man I am talking about is Ramanujuan. I am having a little trouble sorting through it at the moment, since it is very high math (much higher than what I can understand), but it might be something to look at.

lau
Veteran
Veteran

Joined: 17 Jun 2006
Age: 77
Gender: Male
Posts: 9,798
Location: Somerset UK

19 Feb 2012, 6:33 am

Thom_Fuleri wrote:

An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
...
So any prime necessarily much be one of the two remaining options - 6n+1, or 6n+5 (6n-1).
...

To be a bit more pedantic... (

)
Apart from nothing, all prime numbers can be expressed as n.
Apart from 2, all prime numbers can be expressed as 2n+1.
Apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n+5.
...

This approach generalizes: http://en.wikipedia.org/wiki/Primorial

I'd guess that, if working on numbers with a view to establishing their primality, storing values in base 30030 (2*3*5*7*11*13) would give a quick test that eliminated most composites.

_________________
"Striking up conversations with strangers is an autistic person's version of extreme sports." Kamran Nazeer

ruveyn
Veteran
Veteran

Joined: 21 Sep 2008
Age: 89
Gender: Male
Posts: 31,502
Location: New Jersey

19 Feb 2012, 8:41 am

Thom_Fuleri wrote:

An interesting snippet - apart from 2 and 3, all prime numbers can be expressed as 6n+1 or 6n-1.
A little algebra, however, soon explains why.

.

The narrows down where to look for primes. But it is not a prime generator. 6*8 + 1 = 7*7

ruveyn

Page 4 of 8 [ 113 posts ] Go to page Previous 1, 2, 3, 4, 5, 6, 7, 8 Next

Jump to:

Method for generating prime numbers Post Reply New Topic

Method for generating prime numbers