- #1

- 181

- 1

But now I want to know is there any way to find divisbility with any prime number?

Suppose, how can I say 12783461236 is divisible with 97 or not?

- Thread starter Moni
- Start date

- #1

- 181

- 1

But now I want to know is there any way to find divisbility with any prime number?

Suppose, how can I say 12783461236 is divisible with 97 or not?

- #2

Hurkyl

Staff Emeritus

Science Advisor

Gold Member

- 14,916

- 19

- #3

NateTG

Science Advisor

Homework Helper

- 2,450

- 6

Like:Originally posted by Moni

But now I want to know is there any way to find divisbility with any prime number?

Suppose, how can I say 12783461236 is divisible with 97 or not?

Take the last digit, multiply by 29, subtract from the rest, and see if the result is divisible by 97?

It's probably faster to just trial divide.

- #4

- 181

- 1

Can you give any link to proceed on???

- #5

NateTG

Science Advisor

Homework Helper

- 2,450

- 6

Arbitrary precision arithmetic is pretty straightforward.

Google on it for more information.

Google on it for more information.

- #6

- 181

- 1

The google results I've got so far are with traditional division method, there is no use of such type of divisibility testing....

I want to develop one with this feature, then it will be faster than others available with stright forward DIVISION !!!

- #7

NateTG

Science Advisor

Homework Helper

- 2,450

- 6

Observation 1:Originally posted by Moni

The google results I've got so far are with traditional division method, there is no use of such type of divisibility testing....

I want to develop one with this feature, then it will be faster than others available with stright forward DIVISION !!!

The number of operations that you need for a 'traditional' division approach is [tex]log_2 m * log_2 n[/tex] where [tex]m,n[/tex] are the numbers that you're using. That's really fast already. So fast that checking numbers with thousands of digits should not take very long.

Are you trying to do some sort of crypto stuff?

- #8

- 181

- 1

For traditional division I use:

It's not that crypto tech...just making math soft and learning algorithms :)void div(char *s1,char *s2,char *r,char *q)

{

char op1[SIZE],op2[SIZE],res[SIZE],factor[SIZE],x[SIZE],div[SIZE],z[SIZE];

int i,j,l1,l2,ok;

strcpy(op1,s1);

strcpy(op2,s2);

strcpy(res,"0");

strcpy(q,"0");

l1=strlen(op1);

l2=strlen(op2);

for(i=l1-l2;i>=0;--i)

{

strcpy(x,"1");

strcpy(div,"0");

for(j=1;j<=i;++j)

{

x[j]='0';

}

x[j]=0;

mul(op2,x,factor);

while(1)

{

ok=sub(op1,factor,z);

if(ok==-1)

{

strcpy(q,op1);

break;

}

else

{

strcpy(op1,z);

add(div,x,div);

}

}

add(res,div,res);

}

if(l1<l2) strcpy(q,s1);

strcpy(r,res);

}

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 3K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 6

- Views
- 2K

- Last Post

- Replies
- 1

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 2K

- Last Post

- Replies
- 2

- Views
- 3K

- Last Post

- Replies
- 3

- Views
- 2K