Not Yet Answered # prime numbers

ddanbe 2,467 Prashant_3 -3 # include <stdio.h>

# include <conio.h>

android9000 11 Moschops 683 AndrisP 85 iamthwee 1,547 ddanbe 2,467 Slavi 94 Banfa 597 rubberman 1,109

0

Are WE supposed to do that?

it is YOUR assignment, and we will gladly be helping with the code you already have and having problems with.

It all starts with knowing what a prime number is. You know that, don't you?

-2

void main()

```
{
```

int a[100],i,j=2;

clrscr();

for(i=0;i<100;i++)

a[i]=i+1;

printf("Prime Number between 1 to 100 \n");

for(i=0;i<100;i++)

```
{
for(j=2;a[i]>j;j++)
{
if(a[i]%j==0)
break;
}
if(a[i]==j || a[i]==1)
printf("%d\t",a[i]);
}
```

getch();

```
}
```

-1

sieves are much faster because they skip a bunch of numbers. There are three really well known ones linked to from the erastothenes wiki page. They are Atkins (fastest), Sundaram (next best), Erastothenes.

http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

http://en.wikipedia.org/wiki/Sieve_of_Sundaram

http://en.wikipedia.org/wiki/Sieve_of_Atkin

```
class Erastothenes{
//TODO sieve of erastothenes for numbers <= 1,000,000
private:
//initialize array of 1,000,000 potential numbers at 0
static int nums[1000000];
//max: our nth prime
int max;
//the starting point (first is 2 since 1 is prime and everything divisible by 1)
int p;
void perfsift(){
int i=0;
//iterate through the numbers up to our potential maximum
while(i<(max*100) & (p*i)<(max*100))
{
nums[(p*i)]=(p*i);
i++;
}
i=0;
//get the next starting p value if in existance
while(i<(max*100) & nums[i] != 0)
{
i++;
}
//recurse the function if there is an unmarked number greater than the current p
if(nums[i]==0)
{
p=i;
perfsift();
}
}
public:
//empty constructor
Erastothenes(){
max=0;
p=2;
}
Erastothenes(int inmax){
max=inmax;
p=2;
}
//sift through the array
int sift(){
if(max>0)
{
//sift at max*100
perfsift();
//get the remaining numbers, which are prime, up to the nth prime
int j=0;
int i=0;
while(j<max & i<sizeof(nums)){
if(nums[j]==0)
{
j++;
}
i++;
}
if(j<max){
printf("No Prime Found. The prime must be less than %i",sizeof(nums));
}
else{
return i;
}
}
return -1;
}
};
```

3

```
#include <iostream>
int main()
{
std::cout << "2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97" << std::endl;
}
```

-1

```
#include <iostream>
using namespace std;
bool IsPrime(int number)
{
for (int i=2; i<=number/2; i++)
{
if (number % i == 0) return false;
}
return true;
}
int main()
{
for(int i=2; i<=100; i++)
{
cout << i << (IsPrime(i)?" is prime":"") << "\n";
}
system ("PAUSE");
return 0;
}
```

*Edited 2 Years Ago by AndrisP*

1

```
#include <stdio.h>
#include <cstring>
char _[10000000],____[100000000], _____[10000000],__[10000000], *___;
#define ________OOOOOOO________ ___,2+(((((((((((_
#define _____OOO_______OOO_____ 2+(__
#define ___OO_____________OO___ "__"
#define __O____O_______O____O__ ___=_____,"")
#define _O____OOO_____OOO____O_ ___,_+(_
#define O_____OOO_____OOO_____O ____,___)))for(;____
#define O______O_______O______O ___,____)?___+=(__
#define O_____________________O __,_))))?"%d\n":""
#define O____O___________O____O __,"__")),_)):(___
#define _O____OO_______OO____O_ _,"_"));fprintf(stderr
#define __O_____OOOOOOO_____O__ ____,"_");for(;____
#define ___OO______________O___ ____,___);___
#define _____OOO________OO_____ __
#define ________OOOOOOOO_______ ____,"__")
int main() {
strcpy(__O_____OOOOOOO_____O__, strcat(________OOOOOOOO_______,
strcpy(__O____O_______O____O__, strcpy(_____OOO________OO_____,
strcpy(_O____OO_______OO____O_, strstr(___OO_____________OO___,
strcpy(_O____OOO_____OOO____O_, strspn(O_____________________O,
strspn(O_____OOO_____OOO_____O, strcmp(___OO______________O___,
strstr(O______O_______O______O, strspn(_____OOO_______OOO_____,
strcat(O____O___________O____O, strcat(________OOOOOOO________,
strcat(_,"__")))))))))))))));
}
```

Do I win? I also put a bug in it?

0

@AndrisP: calculate: `SQ = sqrt(number);`

(also include math.h of course)

On line 6 of your code change `number/2`

with `SQ`

0

```
#include<iostream>
using namespace std;
void primes(int n){
bool isPrime[n+1];
for(int i=2; i<=n; i++)
isPrime[i]=true;
//
for(int i=2; i<=n; i++){
if(isPrime[i]){
cout << i << " ";
for(int j=2*i; j<=n; j+=i) isPrime[j]=false;
}
}
cout << endl;
}
int main (){
primes(100);
}
```

Congratulations your homework was done .. :D

iamthwee nice one :D

0

It should be noted that for finding primes between in the range 1 - 100 any of the sieves are overkill of a high order.

since 1 is prime

Actually most university level matamaticians no longer think of 1 as prime, it is just a (very) special case. As far as I can tell this is because they had too many theorys/laws that went "for all primes, except 1, X is true" so they changed their minds about 1 being prime.

```
for (int i=2; i<=number/2; i++)
```

Very un-optimised, to start with if you test 2 independantly initially then you can skip testing all the other prime numbers (including ddanbe's suggested optimisation)

```
if ((number % 2) == 0) return false;
int sq = sqrt(number)
for (int i=3; i<=sq; i++)
```

You can take this further and apply a similar optimisation for multiples of 3 noting that every 3rd odd number is a multiple of 3

```
if ((number % 2) == 0) return false;
if ((number % 3) == 0) return false;
int sq = sqrt(number)
int step = 4;
for (int i=5; i<=sq; i+=step)
{
step = 6 - step;
}
```

ddanbe optimisation reduces the number of check steps by a factor of `2 / sqrt(n)`

my optimisation further reduces it by approximately a factor of 1/3 resulting in checking each number for primeality against approximately `2 / 3.sqrt(n)`

less other values. If you were looking for primes in the range 1 - 1000 then you end up performing about 2% of the checks you would have to perform with a straight loop

```
for (int i=2; i<=number/2; i++)
```

*Edited 2 Years Ago by Banfa*

0

Ah, prime numbers! One of my favorite subjects when I was studying public key encryption algorithms back in 1984-1985. I wrote some interesting prime factorization algorithms that were quite efficient so I could generate Goedel numbers from random strings, and extract the strings from the numbers in turn. Over the years, other stuff caught my interest, such as efficient algorithms to distribute computational loads over large networks of dis-similar systems. I'm working a lot in big data analytics today... :-)

*Edited 2 Years Ago by rubberman*

This article has been dead for over six months. Start a new discussion instead.

Recommended Articles

I don’t want at this stage work on a big separate project as I've already got plenty ...

I am writing a java program that needs to execute shell commands, so I wrote a function that would take the command to execute as a string (ie: "mkdir ~/Folder1") and execute that command with the shell. Here is the function:

```
try
{
Runtime run = Runtime.getRuntime();
Process pr = ...
```

Hi. I have a form with list box : lst_product, datagridview : grd_order and button: btn_addline. lst_product has a list of product ids selected from database (MS Acess 2013) , grd_order is by default empty except for 2 headers and btn_addline adds rows to grd_order.

btn_addline :

`Private Sub btn_addline_Click(ByVal ...`