1. ## basic prime numbers

I decided to make a small program that found prime numbers, and after an hour or so of tweaking i came up with something that was about 30 times faster than my first attempt, however I still have a couple of questions:

1. Is there an alternative to goto
2. How else can I optomise it further/any further improvements?
3. It only really needs to test if it is divisible by prime numbers, not every number, is there a way of doing this without taking up too much memory, and if so what shall i use, and will it even be quicker?

Thanks for any help:

Code:

Code:
```#include <iostream>
using namespace std;

// varaiables
int num=0;
int i;
int j;
int main()
{
for (j=1; j <=9999; ++++j)
{
for (i=3; i <((j+1)/2); ++++i)
{
if (j%i==0) goto moo;
}
cout << j <<endl;
moo:;
}
cin >> num;
}``` 2. I was always told not to use goto. You could use 'break', to get out of the loop, then only print the output if i == (j-1)/2.

You could use bit shifting to divide by two, for some processors that works faster, but I think thats just old ones. IE: j>>1 is the same as j/2 3. i tried that option, but wouldnt that mean an extra if command which would probably slow it down? 4. It's a relatively small program, i don't think an extra if statement will make any difference. 5. Therefore double the amount of commands, pointless or not thats exactly what im trying to do; make it as fast as possible. 6. If you want to increase performace - store all found prime numbers and check the division only to these numbers

And of course - the internal loop should go only upto sqrt(j) 7. ok i added that and it has sped it up to a stupid speed xD

Code:
```#include <iostream>
#include <math.h>
using namespace std;

// varaiables
int num=0;
int i;
int j;
double k;
int main()
{
for (j=1; j <=50000000; ++++j)
{
k=sqrt(j);
for (i=3; i <=k; ++++i)
{
if (j&#37;i==0) goto moo;
}
cout << j <<endl;
moo:;
}
cin >> num;
}``` 8. 1) In C++ headers inherited from C are named "c+name" and without ".h". Hence: <cmath>

2) Your varaiables shouldn't be global. Actually you should declare them at the point where you can initialize them at the same time.

3) I'm afraid using the increment operator twice like you do may not give the same result with all compilers. If you want to increment by 2, use
Code:
`i += 2;`
4) Your goto is fine by me if you think this speeds things up. You can make the program faster if you store the primes you have found somewhere and only do trial division with the primes you have found so far (up to the square root).

Code:
```#include <iostream>
#include <cmath>
using namespace std;

int main()
{
for (int j=1; j <=50000000; j += 2)
{
double k=sqrt(j);
for (int i=3; i <=k; i += 2)
{
if (j%i==0) goto moo;
}
cout << j <<endl;
moo:;
}
cin >> num;
}``` 9. I would make all variables unsigned ints here. Certainly k being a double is going to probably mean a real->int conversion every time through the i loop. 10. I'd write the inner loop and surrounding code like this, but that's just me:
Code:
```unsigned long k = (unsigned long)(sqrt(j) + .5);
unsigned long i;

for(i = 3; j &#37; i && i <= k; i += 2);

if(i <= k) cout << j << endl;```
because I think j%i has a greater chance of being true, since the majority of numbers are non primes. Just a thought.

 > I'd make all variables unsigned ints here
Or better yet, unsigned longs, since 50 million can't nessesarily be stored in an int. [/edit] 11. Originally Posted by cakey 1. Is there an alternative to goto
There are algorithms, that can be implemented with 'goto' - and only with 'goto'!

'goto' is a basic jmp command your machine actually is able to understand (literally!).
This is why goto is executed more quickly than most loops, which usually consist of a combination of many machine commands.
So - although you are often told to avoid 'goto' and to use loops instead, 'goto' is the more optimized version in most cases.
But nevertheless it is a good idea to use loops instead of 'goto'.
Ha ha. 12. >> There are algorithms, that can be implemented with 'goto' - and only with 'goto'!
Like what?

If you're learning C++, then you should be learning about making clear, robust code first and foremost. In most cases the goto will will have no noticable positive impact on execution speed, and in most cases it will have a noticable negative impact on coding speed. That's why beginners are taught to avoid it. 13. Originally Posted by Daved >> There are algorithms, that can be implemented with 'goto' - and only with 'goto'!
Like what?

If you're learning C++, then you should be learning about making clear, robust code first and foremost. In most cases the goto will will have no noticable positive impact on execution speed, and in most cases it will have a noticable negative impact on coding speed. That's why beginners are taught to avoid it.
(Of course) (one) (should use) (loops) instead!
Only wanted to show the positive effects of 'goto'. Most tutorials/books say it's the worst thing on earth to use 'goto' in C++ - programs. GOTO is by far not a useless basic command. There is a good reason, why almost every programming language knows the GOTO command. A language without GOTO is NOT TURING COMPLETE. Never.
Ha ha. 14. Hint. Don't look for prime numbers, look for NOT-prime numbers.

it's like this

Code:
```int i,j;

for(i=2;i<=MAX/2;++i)
{
for(j=2;j<=MAX/2;++j)
{
if(i*j>MAX) break;
primes[i*j]=false;
}
}```
Thinking like a physicist (please forgive) all numbers are prime until proved against.

I know this method as "Striking the table", if you multiply two numbers greater than 1, you'll definitely get a non-prime number.

On the computing side: This method is incredibly fast. I used it on an 3Ghz intel (That actually runs slower ) to compute the prime numbers from 1 to 100 millions and took 3 minutes.

From 1 to 20.000, it's about two miliseconds of work.

Good Luck PS:

This line:
Code:
`        if(i*j>MAX) break;`
It's very important. It makes it about a hundred times faster. 15. because I think j&#37;i has a greater chance of being true, since the majority of numbers are non primes. Just a thought.
Here I can think about 3 solutions

j % i && i <= k - because first condition has bigger chance to be false

i <= k && j % i - because the second condition check takes a lot more time than the first

(j % i != 0) & (i <= k) - because we have only one branching - so the branch misses chance is lower

And I'll go for one of them only after profiling...

otherwise - I'll use the code that is easier to read - with "if" inside "for"

Code:
```for(i = 3; i <= k; i += 2)
if(j % i) break;``` Popular pages Recent additions 