Want to create LARGE array of prime numbers(C++)2

Mr. Flibble

Tried to post this as a reply but it wouldn't appear. . ? .

Thanks for the reply. I have cleared ut the code a bit. (I didn't write most of it and dont understand it all) - couldya tell me what the 'argc' bit is doing?

Basically it works fine with small primes(<1M) but crashes above that. Would that be because the array cant hold that much data?

#include <stdio.h>

 int main(int argc, char* argv[])
{
 int HIGH,i;
cout << "Enter HIGH(upper number for primes)\n";
cin >> HIGH;
if(argc == 3)
{
HIGH = atoi(argv[2]);
}
// create and populate the array
int* p = new int[HIGH];
for(int i = 0; i < HIGH; ++i) p[i] = i+1;

for(i = 2; i < HIGH; )	// loop through the integers, starting with 2
{
for(int j = i; j < HIGH; ++j)	// loop through the array
{
if((p[j] != i) && (0 == (p[j] % i))) p[j] = 0;
}
while(p[i++] == 0);	// get the next sieve - this saves a lot of processing
}
for(i = 0; i < HIGH; ++i)
{
		if(p[i] != 0) 
		{
		printf("%2i ",p[i]);
		}
}
}

Dr_Teeth

Why do you need an array of 10 million prime numbers may I ask? Are you constructing this array and then stepping through it somewhere else in your program to do some kind of calculation?

It strikes me as bad practice to allocate such a large amount of memory - why not calculate prime numbers do use them at the same time?

I'm not sure if there are limits on the sizes of arrays - that could be a platform-dependent kind of thing.

Teeth.

Baz_

For a start

#include <stdio.h> 

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

  if(argc == 2)
  {
    HIGH = atoi(argv[1]);
  }
  else
  {
    cout << "Enter HIGH(upper number for primes)\n";
    cin >> HIGH;
  }

main() as I'm sure you already know is a function, and like all functions main can take arguements. When you run a program from the command line (DOS) you can type something like:

c:\>program_name 100

Where you want the program to find the integers up to 100. In this example there are 2 arguements being passed to main the program name argv[0] and the number 100 argv[1] argc in this case should be 2 (I think).

How this works is that when you run a program from the command line it is optional to accept parameters, however if you do the number of parameters you take in is passed in first and placed into the int argc, in this case two.

Then the arguements are stored in the array of char pointers argv, now the first value in the array is always the exact path typed to run the program, and the second is the next string on the line, and the next is the next, and you can keep going depending on your needs. In this case however only two things are being accepted in, the path and the number you want to investigate up to, 100 in this case, taken in as strings.

Right so Ive changed the code a bit because it was doing some unnecessary things, basically if a second value was passed in the program already knows how high to calculate, and you don't need to prompt the user, so I changed the if. I also think that it shoul be two and not three, but I'm not certain on that one. But I'll carry on as if I am, so basically if you already have a number don't prompt if you don't then prompt. The other way was very very very very very very very very very very very very very very very very very bad programming, never take in data, and then over write it without warning.

Next:

  // create and populate the array
  int* p = new int[HIGH];

  for(int i = 0; i < HIGH; ++i) 
    p[i] = i+1;

I assume you know but just in case. This section just initialises the array from 1 = p[0] to p[HIGH-1] = HIGH.

  for(i = 2; i < HIGH ; ) // loop through the integers, starting with 2
    {
    for(int j = i; j < HIGH; ++j)	// loop through the array
    {
      if((p[j] != i) && (0 == (p[j] % i))) 
        p[j] = 0;
    }
   
    while(p[i++] == 0);	// get the next sieve - this saves a lot of processing
  }

  for(i = 0; i < HIGH; ++i)
  {		
    if(p[i] != 0) 		
    {		
      printf("%2i ",p[i]);		
    }
  }
}

Now this code is a bit screwy even for me, but, you're also mixing up languages with your printf's and your cin, cout, and using stdio.h instead of iostream.h. So first of all decide on the language your using and then we can work from there, but anything before this section seems okay, apart from the #includes, but that can be resolved with the language answer.

Baz_

p.s. is this for the sieve of erasthenos(spell??)

[This message has been edited by Baz_ (edited 16-08-2001).]

Hobbes

If your going to have 10 million primes which another function has to use later then instead write them to a file.

Better yet have the program check to see if the file isn't already there and then create the file, otherwise read from the file and your program is even faster.

Also (it's been a while) but a quick way to find a prime is to check every number from 2 to the square root of the number. Anything after the square root would be redundant.

Mr. Flibble

Yup, Dr. Teeth. I guess it would be better to find one prime at a time and then put them through the calculation and move onto the next - but I'm not sure how.

I tried changing the code to what you suggest Baz but I just get a zillion declaration syntax errors...
It seems also that the '3' in 'if(argc == 3)' can be change any number without effecting the program.

Sounds like good idea's Hobbes, em, don't think I've the know how to do it tho.

To make things easier I'll tell you the grand scheme:
I am trying to solve this puzzle. What is the highest prime number that can be multiplyed by another number by adding a '1' to the beginning and end of the number. For example, the lowest prime that you can do this to is 23. 23 x 77 = 1771. The next is 29. 29 x 52631579 = 1526315791.
83 x 137 = 11371
101 x 11 = 1111.
I think its ment to be solved by mathimatical means(not brute force), but this is easier

I have gone about doing this by getting the 1st part of the array of primes and then multiplying it by every integer up to a certain limit. I make the intiger and the result of the multiplication a character string and check:
that the answer begins and ends with 1,
the answer is two characters longer than the integer,
and that the 2nd character of the answer is the same as the first of the integer.

...any better way to do it? without character strings perhaps?

marauder

Another way to spped this up is when setting up the array set p[0]=1 and then
p[i+1]=p+2

then you only get odd numbers in your array as you know evens are not prime anyway.

Your high number now is the number of odd numbers rather than the highest number tested
I suppose you could divide HIGH by 2 if you wanted to...

Hobbes

<font face="Verdana, Arial" size="2">Originally posted by Mr. Flibble:
Sounds like good idea's Hobbes, em, don't think I've the know how to do it tho.</font>

Forgot about the odd numbers

NEW_HIGH = ceil(sqrt(HIGH));
for(i = 0; i < NEW_HIGH; ++i);


(My C++ is rusty though)



[This message has been edited by Hobbes (edited 17-08-2001).]

Mr. Flibble

Hi.

Things are looking good. I've managed to get one program to write the primes to a file and another to read through them and check if they fit the bill.

As I'm looking for the 'highest' prime number that will multiply by another to add a 1 on the begining and end, I think it would make more sense to read from the end of the primes list. Is this possible if I don't know the highest prime in the list(or its buffer number(?))?. I have it saved as a binary file.

Mr. Flibble

Hi. Just to let you know that the problem has been solved. Ans = 101x11=1111. Turns out that such brute computer force wasn't needed. I just realised that if both the prime and the number I multplied it by were both above 1000 then the answer would be 3 or more digits longer than the initial number, if ya get me.